在主字符串中查找子串的KMP算法?和字符串中查找字符用KMP算法的C语言代码-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

在主字符串中查找子串的KMP算法?和字符串中查找字符用KMP算法的C语言代码

知与谁同 2018-07-20 09:58:01 1597
在主字符串中查找子串的KMP算法?和字符串中查找字符用KMP算法的C语言代码
算法 C语言
分享到
取消 提交回答
全部回答(1)
  • 小旋风柴进
    2019-07-17 22:55:59
    /***KMP算法是对蛮力算法的优化,原理很简单。但存在最坏情况,时间复杂度很可能会崩坏到O(m+n)。
    * 推荐在高频度数据查找采用优化的Boyer-Moore算法。
    *以下为代码
    ***/
    /***首先创建一个ADT,这里给出最简形式,省略部分涉及不到的操作***/
    ADT String
    {voidStrAssign(SString &T,char*S)//值为S的串T
    bool SreEmpty(SString &S) //判断空串
    int StrLength(SString &s) //返回长度
    void Concat (SString &T,SString&S1,SString &S2)//返回组合的新串
    void SubString (SString &Sub,SString &S,int pos, int len)//同串则返回第pos后的串的最初位置,否则为0

    }
    /***算法部分***/
    int KMP(char *T,char *p)
    {int n=strlen(T);
    int m=strlen(P);
    int i,j;
    for(i=0;i<n-m;i++)
    {j=0;
    while(j<m&&T[i+j]==P[j])j++;
    if(j==m) return i;
    }
    return -1}
    0 0
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

推荐文章
相似问题
推荐课程