扩展KMP算法

  须要严重注意的是： 在上述的情况（2）中，本该从A[p+1]与B[p-i+1]開始匹配，可是，若p+1<i，也就是p-i+1<0（这样的情况是有可能发生的，当ex[i-1]=0，且前面的ex值都没有延伸到i及以后的时候）的话，须要将A、B的下标都加1（由于此时p必定等于i-2，假设A、B的下标用两个变量x、y控制的话，x和y都要加1）！！！！！

    代码：

int next[maxn],extend[maxn]; //extend[i]表示原串以第i開始与模式串的前缀的最长匹配
void EKMP(char s[],char t[])//s[]为主串，t[]为模版串
{
    int i,j,p,l;
    int len=strlen(t);
    int len1=strlen(s);
    memset(next,0,sizeof(next));
    memset(extend,0,sizeof(extend));
    next[0]=len;
    j=0;
    while(1+j<len&&t[j]==t[1+j])j++;
    next[1]=j;
    int a=1;
    for(i=2; i<len; i++)
    {
        p=next[a]+a-1;
        l=next[i-a];
        if(i+l<p+1)next[i]=l;
        else
        {
            j=max(0,p-i+1);
            while(i+j<len&&t[i+j]==t[0+j])j++;
            next[i]=j;
            a=i;
        }
    }
    j=0;
    while(j<len1&&j<len&&s[j]==t[j])j++;
    extend[0]=j;
    a=0;
    for(i=1; i<len1; i++)
    {
        p=extend[a]+a-1;
        l=next[i-a];
        if(l+i<p+1)extend[i]=next[i-a];
        else
        {
            j=max(0,p-i+1);
            while(i+j<len1&&j<len&&s[i+j]==t[j])j++;
            extend[i]=j;
            a=i;
        }
    }
}

文字来源： 点击打开链接

    这些理论性的东西，看到一半实在是看不下去啦，，抓狂抓狂，，，，还是通过做题目来理解理论分析吧。。。做到对应的题目在加到本博文中吧。