字符串精确匹配KMP算法思想演变
引言
字符串匹配一直是计算机科学领域研究和应用的热门领域，算法的改进研究一直是一个十分困难的课题。作为字符串匹配中的经典算法，KMP算法一直以较高的效率和富有美感的构思闻名。本文希望由传统的精确匹配算法入手，层层推进，研究KMP算法思想的演变历程。
1.传统的精确匹配
1.1 精确匹配的含义
字符串的精确匹配就是在文本T中找出模式P的精确副本。这是一个要么完全匹配要么、完全不匹配的方法。如果模式P和T的一个子字符串非常类似，但不相同，就拒绝部分匹配。
我们首先约定一些符号：文本T是一系列符号、字符或字母，|T|表示T的长度，T(i)是T中位置i上的字符，T(i…j)是T中从位置i开始到位置j结束的子字符串，模式P(指在T中寻找匹配的字串)和文本T中的第一个字符在位置0上。另外，正则表达式a^n表示字符串a….a，其中包含n个a。
1.2 强制匹配
字符串精确匹配最简单的算法即是直观的“暴力破解”，这种称为强制匹配的算法从文本T的第一个字母和模式P的第一个字母开始比较P和T，如果不匹配，就从T的第二个字符开始和模式P的第一个字母匹配，以此类推，不保留在后续尝试中可能有用的信息。伪代码十分常见，就不在此赘述了。
在最坏情况下，强制匹配的执行时间是O(|T||P|)。
1.3 强制匹配的改进
对于强制匹配算法，1992年Hancart提出了一种称为not-so-naive算法的改进。该算法从P的第二个字符开始比较，直到P的结尾，最后比较第一个字符，所以比较过程中的字符顺序是P(1),P(2),…….,P(|P|-1),P(0)。
记录下P的前两个字符相等的信息，并在匹配过程中使用。要区分两种情况：P(0)=P(1)和P(0)!=P(1)。在第一种情况下，如果P(1)!=T(i+1)，就给文本索引i递增2，因为P(0)!=T(i+1);否则，i就递增1。这类似于第二种情况中的P(1)=T(i+1)。这样，就可以移动两个位置。
匹配从第二个字符开始。如果在P(1)和T(i+1)之间又一个不匹配的字符，则只要P的前两个字符是相同的，P就可以移动两个位置，然后开始下一次迭代，因为这种不匹配意味着P(0)和T(i+1)也是不同的。但是，当内层循环中出现不匹配之后，模式只移动一个位置。 而P的前两个字符不同时，采取的措施则相反。
在最坏情况下，该算法的执行时间是O(|T||P|)，但如Hancart所述，它的平均执行性能比起KMP、Boyer-Moore等字符串匹配算法要好。
2. KMP算法
2.1 可以改进什么？
强制算法的效率很低，因为它在找不到匹配的字符后，要把模式P移动一个位置。为了加快算法的执行速度，Hancart的算法允许移动两个字符。但是，我们应该需要一种算法，可以将P向右移动多个位置，同时不遗漏任何匹配。
强制算法效率不高的根源是进行了多余的比较。要避免这种冗余，应该注意模式P在其开头到不匹配的字符之间包含的相同的子字符串，利用这一事实，可以把P向右移动多个位置，之后开始下一次扫描。
2.2 如何改进
从上文可以看出，一般情况下，当T(K+1)与P(j+1)发生不匹配，而P(0…j)都已经完成匹配时，我们可以尝试在P(0…j)中寻找与其后缀相匹配的前缀，假设匹配的前后缀字串的长度都是len，即P(0…len-1)和P( j-len+1….j )是两个相同的字串，前缀从P的开头起始，后缀以P的结尾结束，长度都是len，它们有相同的内容。
因为P(0….j)已经完成了匹配，故T(K-len+1…K)与P(j-len+1….j)是匹配的，而P(j-len+1….j)与P(0…len-1)是匹配的。所以P(0…len-1)与T(K-len+1….K)是匹配的，当T(K+1)与P(j+1)不匹配时，我们可以不用像强制算法要求那样将P(0)与T(K-j+2)重新开始匹配，可以将P(len-1)与T(K)对齐，从P(len)与T(K+1)开始比较。
由之前的论证可以知道，这样是没有错误的，P(0…len-1)已经完成匹配。而由于P(len…j-len)中在之前的子串匹配中已知无法与T(K-len+1…K)中某一子串匹配，故无法完成模式匹配，可知P(len-1)与T(K)对齐没有遗漏或是跳过可能的模式匹配的情况。
在匹配过程中，P与T会多次不匹配，此时就需要移动P或T使之到指定的位置，上述的信息将会使用多次。因此，P应该进行预处理。重要的是，在这种方法中，只使用有关P的信息，T中字符的配置无关紧要。
定义表next：
- 当j=0时，next[ j ]= -1；
- 如果k存在，next[ j ]= max{k：0< k <j，P[0...k-1] = P[j-k...j-1] }；
- 其他，next[ j ]= 0 。
也就是说，next[ j ]表示子字符串P(0…j-1)中与相同字符串前缀匹配的最长后缀的长度。
条件k<j表示前缀也是一个正确的后缀，但这里由于P[0...k-1]，我们不接受同是前缀和后缀的子串。没有这个条件，P(0...2)=aab 的 next[2] 应该是2，因为aa既是aa的前缀也是后缀，但有了这个条件，next[2] = 1而不是2。
同是应该注意重叠的情况，比如ababa最长匹配的后缀是aba，长度为3。
假设我们现在已经获得了处理模式P得到的next数组，至于处理方式，我们稍后再谈。由强制匹配算法的伪代码我们可以较容易的得到Knuth-Morris-Pratt算法的伪代码：
1.Kunth-MorrisPratt(模式 P，文本 T)
2. findNext(P,next);
3. i = j = 0;
4. while i <= |T| - |P|
5. while j == -1 or (j<|P| and T[ i ] == P[ j ])
6. i++;
7. j++;
8. if j == |P|
9. return 在i - |P|处的匹配;
10. j = next[ j ];
11. return 没有匹配;
````
i 标记了文本T正在匹配的字符位置，j 标记了模式P正在匹配的字符位置。当 j == -1时，正在进行模式P的第一个字符匹配，无字符完成匹配，因此进入匹配过程。当 j < |P| 时，说明匹配未完成， 尝试对比P[ i ] == P[ j ]。若匹配，则更新i 和 j 的值，执行下一对字符的匹配；若失败，则此次匹配失败，跳出循环。跳出循环后，判断 j 是否等于 |P|，若等于，则说明P[0…|P|-1]都已经完成匹配，即模式P完成精确匹配，从文本T的 i - |P| 处开始达成精确匹配。若不等于，则匹配未完成，且在P[ j ] 和 T[ i ]处失败，根据之前的论述，此时我们可以查询next数组，将P[next[ j ]]与T[ i ]对齐，然后继续执行匹配直到 i>|T|-|P| ，此时文本T已比较完，没有可与模式P匹配的字串，匹配失败。
注意，在比较过程 i 只会递增或是不变，不会减少。
###2.3 求next数组
表next仍然没有确定，我们可以使用强制算法来确定它，对于短模式而言，效率并不算低。还可以使用KMP算法提高确定next的效率。
next包含P的匹配前缀中最长后缀的长度，即P的一些部分与P的其他部分匹配。但匹配问题已经使用KMP算法解决了，在这种情况下，P再次与其自身匹配。但是，KMP使用的是目前仍未知的next。所以，必须修改KMP算法，使之使用已经找到的值确定next的值。设next [0] = -1,假定next[ 0 ],…next[i-1],应该考虑两种情况：
+ 在第一种情况下，我们要找出匹配前缀的最长后缀，只要把字符P[i-1]与对应于位置next[i-1]的后缀关联起来，当P[i-1]=P[next[i-1]]时，它为真：
在这种情况下，当前的后缀比前面找到的后缀多一个字符，所以next[ i ] = next[ i-1 ]+1。
+ 在第二种情况下，P[i-1] != P[next[ i-1 ]]。但这只是一个不匹配的字符，不匹配可以用表next做处理，这就是要确定它的原因。因为P[next[i-1]]是一个不匹配的字符，所以要检查next[next[i-1]]，确定P[i-1]是否匹配，如果匹配，就给next[i]赋值next[next[i-1]]+1。
否则，就比较P[i-1]和P[next[next[next[i-1]]]]，如果字符匹配，就使next[ i ] = next[next[next[i-1]]]+1，否则，继续搜索，直到找到一个匹配，或达到P的开头为止。
确定表next的算法如下：
````
1.findNext(模式 P，表 next)
2. next[ 0 ] = -1;
3. i = 0;
4. j = -1;
5. while i < |P|
6. while j==0 或 i < |P| 且 P[i] == P[j]
7. i++;
8. j++;
9. next[ i ] = j;
10. j = next[j];
````
###2.3 next数组的改进
如果去除不必要的比较，就可以改进Knuth-Morris-Pratt算法。如果在字符T[i]和P[j]处出现不匹配，下一次就应该尝试匹配字符T[i]和P[next[j]+1],但如果P[j]=P[next[j]+1],则还会发生不匹配，这意味着一次多余的比较。
因此，我们应该重新设计表next，去除这种多余的比较。这里可以使用扩展next定义的方法，再加上一个条件，得到一个更强健的next列表：
1. 当j=0时，next[j]=-1;
2. 如果K存在的话，next[j]=max{k:0<k<j,P[0...k-1]=P[j-k...j-1],
P[k+1]!=P[j]};
3. 其他，next[ j ]= 0。
为了计算nextS，算法findNext()需要考虑新加的条件，略作修改：
````
1.findNextS(模式 P , 表 nextS)
2. nextS[0] = -1;
3. i = 0;
4. j = -1;
5. while i < |P|
6. while j==-1 或 i < |P| 且 P[ i ] == P[ j ]
7. i++;
8. j++;
9. if P[i] != P[j]
10. nextS[i] = j;
11. else nextS[i] = nextS[j];
12. j = nextS[j];
````
### 3.运行时间分析
为了评估Kunth-MorrisPratt()的运行时间，注意外层循环执行了O(|T|)次。而因为在每次的循环迭代中，i都递增，根据外层循环的条件，i的最大值是|T|-|P|，所以内层循环至多执行|T|-|P|。但对于不匹配的字符T[ i ]，j赋予新值的次数是k < |P|。此时，P中第一不匹配的字符与字符T[i+k]对齐。
对于i，可以执行|P|次比较，但每个i不一定都会执行|P|次比较，只有第|P|个i才会如此。所以不成功的比较次数最多为P(|T|/|P|)=|T|。给这个数字加上至多|T|-|P|次成功的比较次数，就得到了运行时间O(|T|)。
而findNext()与Kunth-MorrisPratt()十分相似，所以，可以推测出next可以在O(|P|)时间内确定。Kunth-MorrisPratt()中外层while循环的运行时间是O(T)，所以Kunth-MorrisPratt算法，包括findNext()在内，执行时间是O（|T|+|P|）。
注意，在分析这个算法的复杂度时，我们未考虑文本T和模式P中的字符，也就是说，该复杂度是独立于组成P和T的不同字符数。
