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
     
       2 #include
      
        3 #include
       
         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
        
         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\n",len/(len-next[len-1]));30         else31             printf("1\n");32     }33     return 0;34 }