题目：点击打开链接
终于学会kmp了。
嘻嘻嘻。
不过比这更高兴的是看小姐姐学习看了一晚上。
好了，小姐姐走了，整理下第一个用kmp写的题。（求小猫起名字？pku的背景都这么怪异？）
就是看这篇看会的（写的很棒）：http://www.61mon.com/index.php/archives/183/
#include<stdio.h> #include<string.h> const int max=400005; char str[max]; int len,next[max],ans[max]; /* 生成next数组,记录的是第i个字符之前的序列的 最长序列前后缀长度*/ void get_next(){ int i=0,j=-1; next[0]=-1; while(i<len){ if(j==-1||str[i]==str[j]){ /*首尾作比较，相同再比较下一个。*/ i++; /*-1的时候是这个字符与第一个相同，后面开始[i]==[j]的时候就存入next*/ j++; /*首字符不一样时，每次做完这个j都是变为0的，以至于可以进行下一个的判断*/ next[i]=j; } else j=next[j]; /*判断这个i是不会艹的，但可以让j变成-1，然它能进行if语句进行next的赋值。*/ } /*而且这句else一旦不一样时可以慢慢倒回去，直到倒到-1为止（但一个一个往回倒，这有点蠢啊）*/ } main(){ while(scanf("%s",str)!=EOF){ len=strlen(str); get_next(); /*for(int i=0;i<=18;i++) printf("%d=%d\n",i,next[i]);*/ ans[0]=len; int n=0,i=len; while(next[i]>0){ /*我去，这个可以啊，最长前后缀序列里的最长前后缀序列一定是原字符串的前后缀序列（好绕）*/ ans[++n]=next[i]; /*充分利用next数组*/ i=next[i]; //printf("%d\n",next[i]); } for(i=n;i>=0;i--) printf("%d ",ans[i]); printf("\n"); } }
