当前位置:首页 > 知识点 > kmp

kmp

对于两个字符串的匹配问题 库函数带有strstr 但是效率不高

然后有kmp等算法 会减少匹配需要的时间 因为它会把之前的匹配信息用上 进行跳跃

这里有篇不错的文章 http://blog.csdn.net/v_july_v/article/details/6111565

例题 kuangbin大佬的习题 https://vjudge.net/contest/70325#overview

void getNext()
{
方法1
    int index;
    Next[0]=-1;
    for(int i=1;i<m;i++)
    {
        index=Next[i-1];
        while(index>=0&&s[i]!=s[index+1])
            index=Next[index];
        if(s[i]==s[index+1])
            Next[i]=index+1;
        else Next[i]=-1;
    }
   //如果不匹配 需要跳跃 这个求next需要这样跳 j=Next[j-1]+1;
方法2
/*
    int k=-1,i=0;
    Next[0]=-1;
    while(i<m)
    {
        if(k==-1||s[i]==s[k])
        {
            i++;k++;Next[i]=k;
        }else k=Next[k];
    }

    这个 j=Next[j];
*/
}

int kmp()
{
    getNext();
    int i=0,j=0;
    while(i<n&&j<m)
    {
        if(o[i]==s[j])
        {
            i++;j++;
        }else if(j==0)
        {
            i++;
        }else
        {
            j=Next[j-1]+1;
        }
        if(j==m){
            默认了原串了匹配串是从0开始
            
            这里代表在原串中已经找到了以i-j为首 长度为j 匹配到的串
            如果是问 匹配串中在原串中第一次匹配的位置 那就是i-j
            如果问 匹配串在原串中 一共有多少个匹配串 那 进来一次肯定就cnt++  然后就对j进行处理  比如 原串aaaa 子串aaa 如果我们认为只算1次的话 那就j=0   如果算两次就是j=next[j](用方法二构造)看你怎么先构造的next数组
            数据处理因问题而异
        }
    }
    return -1;//没有匹配到
}



除特别注明外,本站所有文章均为whppmy原创,转载请注明出处来自http://www.dengwenhuo.cn/?id=452

发表评论

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。