在数据结构课上老师讲了kmp算法，但当时并没太懂，现在把思路重新理一遍。
1.kmp算法简介
KMP是三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。
KMP算法其实就是一种改进的字符串匹配算法，关键是利用匹配后失败的信息，尽量减少模式串（W）与主串（T）的匹配次数以达到快速匹配的目的。具体实现就是实现一个next() 函数，函数本身包含了模式串的局部匹配信息。时间复杂度 O(m+n)。
如果考虑最笨的方法，我们可以将T[0]和W[0]进行匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时我们会丢弃前面的匹配信息，然后把T[1]跟W[0]匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，时间复杂度为O(m*n)。
KMP算法利用已经部分匹配这个有效信息，保持i指针（主串）不回溯，通过修改j指针，让模式串尽量地移动到有效的位置，具体可见下面一个例子。
如果主串为：a b c a b c d h i j k
模式串为：a b c e
当我们匹配到主串的第四个字符a时，可知a和e不相等，因此需要移向下一位，但其实我们并不需要从模式串中的第一位重新开始比较，因为主串中的前三个字符已经没有未匹配的a了，不可能匹配成功。
2.next（）函数
因此，最关键的是找到如何移动j指针。我们记当匹配失败时，j要移动的下一个位置为k（即next[j]= k)。记P为模式串。
很显然，存在这样一个性质：最前面的k个位置（对于模式串来说）和j之前的最后k个字符（主串）是一样的。因此得到公式：
P[0 ~ k-1] == P[j-k ~ j-1]
当P[k] == p[j]时
有P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]，即：P[0 ~ k] == P[j-k ~ j]，因此可得
next[j+1] == k + 1 == next[j] + 1
当P[k] != p[j]时
我们只能在0~k-1中去寻找最长后缀串了，因此为
k = next[k]
使用C++ 实现next函数为
int* getNext(string p)
{
int* next = new int[p.length()];
next[0] = -1; //while the first char not match, i++,j++
int j = 0;
int k = -1;
while (j < (int)p.length() - 1)
{
if (k == -1 || p[j] == p[k])
{
j++;
k++;
next[j] = k;
}
else
{
k = next[k];
}
}
return next;
}3.完整算法
int KMP(string T,string p)
{
int i=0;
int j=0;
int* next=getNext(T);
while (i < (int)T.length() && j < (int)p.length())
{
if (j == -1 || T[i] == p[j])
{
i++;
j++;
}
else
{
j=next[j];
}
}
if (j == (int)p.length())
{
return i-j;
}
return -1;
}