kmp的详解在百度上有许多博客群雄辩舌，各有千秋。看着那些证明和解释实在吓人，太长了，今天回顾kmp发现自己已经忘的差不多了，去看百度也不愿意看，就给自己做个笔记，方便以后好回忆，再也不用被那些长篇大论吓到了。
回忆第一步：算法用途
在字符串1中找是否存在字符串2，eg：abxabwabxad中是否有abxad。
回忆第二步：为什么要用算法
暴力不行吗？呃呃呃，Time Limited。
回忆第三步：节省时间的想法是什么
每次暴力都产生了很多有用信息，比如第一次匹配到字符串2的最后一位发现不同后，我们不必从字符串1的b开始找，可以从第二个a开始找。
回忆第四步：怎么实现想法
有一个next数组。
回忆第五步：这数组干嘛用的
next[i]表示字符串1中起点为0，终点为i的子串的最大前缀与后缀相同位数。
回忆第六步：巴拉巴拉的缀是啥东东
字符串eg：ababc，前缀是：a,ab,aba,abab 后缀是:c,bc,abc,babc
ababa的最大前缀与后缀相同位数是3，aba
回忆第七步：这数组怎么求，呃，要不暴力
不用暴力，用一个标记k，遍历一遍字符串就可以了。
回忆第八步：遍历一遍是怎么做到的，死狗欸
好吧，回忆不起来了，那去看别人博客吧。
过了一会儿。。。。
好长啊，还是自己推吧。
k可以初始化为0也可以初始化为-1。我用0吧。k是用来计数，既然用来计数我喜欢从0开始计算。
原理很简单，就是两个指针同时移动，指针i会一直往后走，任性，而k是有变化的。k的计数可以来帮k确定位子。
比较时有两种情况，第一种呢是如果两个指针指的字母相同，这说明前缀和后缀相同的位数可以加一位了，嘿嘿，k++。
另一种情况呢，就是悲剧了，不相同，前缀和后缀不相同了，那k我要去哪呀，可谓何去何从？又回到最初的起点？不对不对，回到最初点是最糟糕的情况，你应该回到你刚刚上一步匹配到的巴拉巴拉缀那里去，即next[k-1]，因为说不定回到这里又能和当前i匹配到了呢，不是吗，于是，你就乖乖用了一个while实现了这一步。走到最后你就把next数组求完了，时间复杂度为i的范围O(n)，效率杠杠的。
回忆结束，打坐休息。。。。
敲得嘛得，不用实战训练一下吗？代码都还没给出来呢？不用实战我学这算法干嘛？我学这算法有何用？
呃呃呃，就拿一题简单的求next数组的题来过过。
题目链接：http://poj.org/problem?id=2406
题目大意：定义字符串的乘法为a*b=a*b，a^4=aaaa,给出一个长度不超过一百万的字符串，求这字符串为某子串的最大幂。
解题思路：所谓高手过招，只需一眼，因为我不是高手，我用了两眼
第一眼：求next数组，得出某子串的长度为n-next[n-1]，n是输入字符串的长度
第二眼：求幂；如果n是子串长度的整数倍，说明可以幂，输出幂，否则该子串不能幂得到原串，即子串就是原串，输出1。
最后献上ac代码（内含next数组求法标码）：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 const int maxn=10000007; 6 int next[maxn]; 7 char str[maxn]; 8 void initnext(int len) 9 { 10 int k=0; 11 for(int i=1;i<len;i++) 12 { 13 while(k>0&&str[k]!=str[i]) k=next[k-1]; 14 if(str[k]==str[i]) k++; 15 next[i]=k; 16 } 17 return; 18 } 19 int main() 20 { 21 while(~scanf("%s",str)) 22 { 23 if(str[0]=='.') 24 break; 25 memset(next,0,sizeof(next)); 26 int len=strlen(str); 27 initnext(len); 28 if(len%(len-next[len-1])==0) 29 printf("%d ",len/(len-next[len-1])); 30 else 31 printf("1 "); 32 } 33 return 0; 34 }