【面向打野编程】——KMP算法入门

一、问题

　　咱们先不管什么KMP，来看看怎么匹配两个字符串。

　　问题：给定两个字符串，求第二个字符串是否包含于第一个字符串中。

　　为了具体化，我们以 ABCAXABCABCABX 与 ABCABCABX为例。

正所谓：暴力出奇迹，枚举是真知。（大雾）先把代码敲出来再说，后面的事后面再考虑。

暴力/朴素匹配：时间复杂度O(N*M)

　　虽然能够得到结果，但是速(bi)度(ge)太低。多看几遍就觉得这里出现了太多无用的计算，每次匹配失败就移动一格，实在挤牙膏。

　　如果我们在每次匹配失败时多移动几位？

二、加速

KMP匹配：时间复杂度O(N+M)

　　每次移动多一点，匹配速度快一点。在已经匹配过的字符串中，上面有部分的字符串与下面字符串的前面几个元素相同。

　　利用已知字符，减少移动次数，比较未知字符，加快匹配速度。（KMP算法的思想）

　　在每次的匹配中，已匹配的字符总是与下面字符串的前面部分（前缀）相同，又与上面字符串已匹配过的部分后面（后缀）相同。可以完全匹配的字符串都在下面的字符串中（废话）。

　　因为只有每次匹配失败的时候才需要移动字符串，因此我们用一个fail/next/爱叫啥叫啥数组来记录移动的终点（下标）。

三、fail/next/爱叫啥叫啥数组

　　开辟一个fail数组，fail[i]表示在匹配word[i]失败时，i需要跳转前往的下标。

　　fail[i]也可表示word[0]~word[i-1]的最长公共前缀后缀长度。

　　如果i跑到-1则表示：word字符串不想与你说话并把你踢出了队伍。

　　来个循环，不断寻找自己的最长公共前缀后缀。由前面的匹配确定后面的fail数组的值，匹配失败直接使用fail数组（已确定的fail值）。

　　　　"ABCA" 最长公共前缀后缀长度为1，即"A"。

　　　　"ABCABC" 的最长公共前缀后缀长度为3，即"ABC"。

　　　　………………

1 void setFail(){
2     int i = 0, j = -1;
3     while (i < wLen){
4         if (j == -1 || word[i] == word[j]) fail[++i] = ++j;
5         else j = fail[j];
6     }
7 }

四、动手

匹配的时候，有问题，找fail，看题目，改条件。

 1 void setFail(){
 2     int i = 0, j = -1;
 3     while (i < wLen){
 4         if (j == -1 || word[i] == word[j]) fail[++i] = ++j;
 5         else j = fail[j];
 6     }
 7 }
 8 int fid(){
 9     int i = 0, j = 0;
10     while (i < tLen){
11         if (j == -1 || a[i] == word[j]) ++i, ++j;
12         else j = fail[j];
13         if (j == wLen){/*该做啥就做啥*/}
14     }
15     return -1;
16 }

开始匹配

然后来一波入门题

POJ 3461/HDU 1686，HDU 2203，HDU 2594，HDU 1711

本渣才学疏浅，璞玉难琢，望各位神犇不吝赐（da）教（lian）。