经典KMP算法回想

经典KMP算法回顾

 

详细内容可以看百科：http://baike.sogou.com/v592179.htm 

我主要讲自己的理解

KMP是字符串的模式匹配算法，时间复杂度为O(m+n)即O(n)

通过下面的代码进一步分析：

#include<stdio.h>
#include<string.h>
#define MM 50005

int next[MM];
char s[MM];//模拟串
char t[MM];//匹配串
/************************************************
next[]表示到当位前的串的前缀和后缀最长匹配长度
eg：s:         a b c a b c d a b c
对应的next[]={-1,0,0,0,1,2,3,0,1,2,3}
如何做的呢？
*************************************************/
void getnext()
{
    int i=0,k=-1;
    next[0]=-1;
    int len=strlen(s);
    while(i<len)
    {
        if(k==-1||s[i]==s[k])
        {
            i++;
            k++;
            next[i]=k;
        }
        else
            k=next[k];
    }
}
/*****************************************
匹配：和求next数组的方法类似;
KMP可以用来求模拟串在主串中出现的位置，不
存在的情况返回-1;也可以用来求最长前缀和后
缀问题，也可以找循环节;
t: abcabcabcdabcabcdabc
s: abcabcdabc
next:-1,0,0,0,1,2,3,0,1,2,3

//下面实现下第二的功能
*****************************************/
void kmp()
{
    int i=0,j=0;
    int lens=strlen(s);
    int lent=strlen(t);
    while(i<lent && j<lens)
    {
        if(j==-1||s[j]==t[i])
        {
            i++;
            j++;
        }
        else
            j=next[j];
    }
    if(!j)printf("0\n");
    else
    {
        s[j]='\0';
        printf("%s %d\n",s,j);
    }
}
int main()
{
    while(scanf("%s%s",s,t)>0)
    {
        getnext();
        kmp();
    }
    return 0;
}

那么如果想看懂了，想练手的可以点击>>这里<<提交代码。

 

题意：给定两个字符串s1 , s2找到s1的最长前缀等于s2的后缀