字符串匹配问题
首先我们先把问题明确一下，给定两个字符串P[1..P.len]和S[1..S.len]，找出P在S中第一次出现的位置L，即最小的L满足P[1..len]=S[L..L+len-1]。例如”HA”在”WAHAHA”中第一次出现的位置是3（这一节约定下标都是从1开始）
暴力算法
从小到大枚举L，然后判断P[1..len]=S[L..L+len-1]的条件是不是满足；不满足就+1试下一个L。伪代码如下：
Match(P,S)
For L = 1...S.len - P.len + 1
Found = True
For i = 1...P.len
If P[i] ! = S[L + i - 1]
Found = False
Break
If Found
Return L
Return -1用一张图来展示暴力匹配的过程：
上图中第一行的字符串是S，第二行的字符串是P。同时第2行也是枚举L=1时的匹配过程，前5个字符abbba都匹配上了；但是第6个字符失配了。第3~5行是枚举L=2, 3, 4时的匹配过程，都是第一个字符就失配了；第6行是L=5时的匹配过程，第一个字符a匹配上了，第二个字符失配了
KMP算法
首先我们定义一个函数：失配位置f(x)。f(x)=k表示当L=x时，失配的字符是S[k]。注意这个位置是在字符串S上的，而不是P上的。在上面的例子中，f(1)=6, f(2)=2, f(3)=3, f(4)=4, f(5)=6
KMP算法的优化思路就是，枚举L的过程中，跳过使失配位置减少的L。例如我L=1的时候已经辛辛苦苦匹配上5个字符S[1..5]了，在第6个字符失配，也就是f(1)=6。那么失配之后能不能至少从L=5开始匹配，跳过L=2..4。因为L=2..4时，f(2)f(3)f(4)都比f(1)还小。好歹f(5)等于f(1)，所以从L=5开始匹配
跳过使失配位置减少的L还有一个好处，就是从L=x跳到L=y时，其实并不用从S[y]开始匹配，而是直接从S[f(x)]开始匹配即可
在上图的例子中，L=1时，在f(1)=7失配。这时我们跳到L=4继续(为什么在L=4继续，看上面一段文字)，注意继续时我们并不用再比较P[1]和S[4]，P[2]和S[5]， P[3]和S[6]，而是直接比较P[4]和S[f(1)]（S[f(1)] = S[7]）
如上图所示，如果L=x时，P[1..100]与S[x..x+99]匹配上。那么L=x+1时，P[1..99]能与S[x+1, x+99]匹配上当且仅当P[1]=P[2]=P[3]=P[4]=…=P[100]，也就是P[1..100]是aaaa….a这样类型的
同理，L=x+2时，P[1..98]能与S[x+2 … x+99]匹配当且仅当P[1]=P[3]=P[5]…=P[99]且P[2]=P[4]=P[6]=…P[100]，也就是P[1..100]是ababab…ababab这样类型的。再同理，L=x+3时，P能匹配到S[x+99]的位置当且仅当P[1..100]是abcabcabc…abcabc这样类型的
用更一般的话说，如果在L=x时，P[1..K]匹配上了S[x..x+K-1]；那么当L=x+d时，P和S匹配的两段是P[1..K-d]匹配S[x+d .. x+K-1]，而S[x+d .. x+K-1]又等于P[1+d..K]（根据L=x时的匹配）。所以在P[K+1]失配时，KMP的思路是，找一个最小的d满足P[1..K-d]=P[1+d..K]
形象的说也就是找到P[1..K]的一个最长前缀，并且这个前缀同时也是P[1..K]的一个后缀，也就是P[1..K]的前j个字符组成的字符串和后j个字符组成的字符串相等
比如P[1..6]=”aaaaaa”，那么这个（同时也是后缀的）最长前缀是P[1..5]=”aaaaa”；如果P[1..6]=”abaaba”，那么这个（同时也是后缀的）最长前缀是P[1..3]=”aba”；如果P[1..6]=”ababab”，那么这个（同时也是后缀的）最长前缀是P[1..4]=”abab”……
如果我们知道P[1..K]的（同时也是后缀的）最长前缀是P[1..j]，我们就记作next[K]=j。这个next数组也叫作next函数。对于一个字符串P来说，我们可以先手算出对应next数组，例如”bababb”的next=[0, 0, 1, 2, 3, 1]
有了next数组，就意味着我们可以达成KMP的优化思路：
- 当匹配P[1..K]与S[x..x+k-1]都成功，而P[K+1]与S[x+K]失配时
- 通过将P[next[K]]对准S[x+k-1]，实现跳过使失配位置减少的L
- 继续比较P[next[K]+1]与S[x+K]，而不用从P[1]开始比较
有了next数组，KMP匹配的伪代码是这样的。注意我们特别让next[0]=-1：
j = 0
For i = 1...S.len
{
//这时p[j]与S[i-1]是匹配上的，尝试匹配P[j+1]与S[i]
while(j >= 0 && S[i] != P[j + 1])
j = next[j]
j = j + 1
if(j == P.len)
return i - P.len + 1
}用图示来展示KMP的过程（已知next数组）：
上图从第三行开始匹配，注意是P[j+1]匹配S[i]，所以一开始S[1..5]匹配上P[1..5]。这时i=6，j=5开始尝试匹配S[6]和P[6]，匹配失败，j = next[j]=next[5]=3
于是第4行尝试匹配S[6]和P[j+1]=P[4]，成功。之后一直成功匹配到S[7]和P[5]。这时S[8]和P[6]匹配失败，j = next[j]=next[5]=3
于是第5行尝试匹配S[8]和P[4]，失败。j = next[j]=next[3]=1。于是第6行尝试匹配S[8]和P[2]，失败。j = next[j]=next[1]=0。于是第7行尝试匹配S[8]和P[1]，失败。j = next[j]=next[0]=-1。这时j=-1会跳出while循环，j++使得j=0。然后进行下一次i=9的循环
于是第8行i=9, j = 0，尝试匹配S[9]和P[1]，成功。之后一直成功匹配到S[13]和P[5]。这时S[14和S[6]匹配失败，j = next[j]=next[5]=3
于是第9行，S[14]匹配P[4]成功，S[15]匹配P[5]成功，S[16]匹配P[6]失败，j = next[j]=next[5]=3。于是第10行，S[16]匹配P[4]成功，S[17]匹配P[5]成功，S[18]匹配P[6]成功，这时找到了一个完成的匹配
假设已知next数组，KMP算法的复杂度显然就是O(i变化的总量+j变化的总量)，其中i是从1~S.len，显然一共变换O(S.len)次。J会通过j=j+1变大，也会通过j=next[j]变小。不过j变大的次数与i循环次数一样都是O(S.len)次，而每次j变小最小变到-1。所以j减小的总量最多是S.len+1，也是O(S.len)
