KMP中的next数组

KMP算法首先要构造匹配子串的数组。假设有两个字符串，一个是待匹配的字符串,一个是要查找的匹配子串。现在我们要在中去查找是否包含，用来表示遍历到了哪个字符，用来表示匹配到了哪个字符。假如,那么就要回到字符处。 中保存的是该失配字符的前一个字符在前面出现过的最近一次失配的字符后面的一个字符的位置
假如字符E失配，那它要返回字符3(D),有什么发现，E到D之间有ABC，D之前也有ABC。再假如字符6（C）失配，它返回字符2（C）,发现6字符前有AB，字符2前也有AB。是不是失配前一个字符加上几个字符会等于这个字符的前缀呢！对的，next的数组就是记录j字符的前一个字符串的字符前缀与字符后缀最大相等长度。

next数组的构建

请仔细对比这两个图。
我们发现一个规律：
当时，
有
其实这个是可以证明的：
因为在之前已经有
(）
这时候现有，我们是不是可以得到。
即：，即。

void getnext(int len)
{
    int j=0;
    int k=-1;
    nxt[0]=-1;
    while(j<len)
    {
        if(k==-1||s[j]==s[k])
        {
            j++;
            k++;
            nxt[j]=k;
        }
        else
        {
            k=nxt[k];//窗口
        }
    }
}

哪next数组还有什么用呢？
next数组一直往前走，得到的所有前缀也是当前主串的后缀，当然了，也是当前主串的前缀。

如果到位置 ，如果有 % , 那说明字符串开始循环了，并且循环到 结束，为什么这样呢？
我们先假设到达位置 的时候，字符串循环了（到完毕），那么如果到第个字符的时候，失配了，根据数组的求法，我们是不是得回溯？
然而回溯的话，由于字符串是循环的了（这个是假定的）， 是不是指向上一个循环节的后面一个字符呢？？是的，上一个循环节的末尾是 ，然后现在循环节的末尾是 ，然么循环节的长度是多少呢？
所以，我们有 就是循环节的长度（假设循环成立的条件下），但是我们怎么知道这个循环到底成立吗？
现在我们已经假设了 循环了，那么我们就一共有 个字符了，如果有 % ，总的字符数刚好是循环节的倍数，那么说明这个循环是成立的。当然,%=0,所以还要确保;

• 周期性字符串⇔ % && ，循环节长度是。
  
• next数组往前跳的步长是一样的，除了最后一次。即
  

HDU-3746Cyclic Nacklace

将字符串弄成至少两个循环节（保证最后是循环节）至少要添加多少个字符。若本身有至少有两个循环节且最后是循环节结尾就输出0.

#include<bits/stdc++.h>
using namespace std;
const int M=101000;
char s[M];
int nxt[M];
void getnext(int len)
{
    int j=0;
    int k=-1;
    nxt[0]=-1;
    while(j<len)
    {
        if(k==-1||s[j]==s[k])
        {
            k++;
            j++;
            nxt[j]=k;
        }
        else
        {
            k=nxt[k];
        } 
    }
}
int main( )
{
    int t;
    scanf("%d",&t);
    getchar( );
    while(t--)
    {
        scanf("%s",s);
        int len=strlen(s);
        getnext(len);
        if(nxt[len]!=0)
        {
            int k=len-nxt[len];
            if(len%k==0&&len/k>=2)
            {
                printf("0\n");
            }
            else
            {
                printf("%d\n",k-len%k);
            }
            
        }
        else
        {
            printf("%d\n",len);
        }
        
    }
    return 0;
}

HDU-1358Period

输出以每个字符结尾能构成周期

#include<bits/stdc++.h>
using namespace std;
const int M= 1000000;
char s[M];
int nxt[M];
void getnext(int len)
{
    int j=0;
    int k=-1;
    nxt[0]=-1;
    while(j<len)
    {
        if(k==-1||s[j]==s[k])
        {
            j++;
            k++;
            nxt[j]=k;
        }
        else
        {
            k=nxt[k];
        }
    }
}
int main( )
{
    int n;
    int k=0;
    while(~scanf("%d",&n)&&n)
    {
        k++;
        getchar( );
        scanf("%s",s);
        getnext(n);
        printf("Test case #%d\n",k);
        for(int i=1;i<=n;i++)
        {
            if(i%(i-nxt[i])==0&&nxt[i]!=0)
            {
                printf("%d %d\n",i,i/(i-nxt[i]));
            }
        }
        printf("\n");
    }
    return 0;
}