KMP
KMP是一个给人捧滥了的算法，其实单看同时有三个发明人这点，就知道这个算法是自古华山一条路，没别的想法的。KMP的算法每步虽然难想但是自然有道理，没有别的方法的。不像排序算法，一嘟噜的算法还没完。根据各种侧重点不同有不同的算法可用。
KMP的比较算法核心在于不回朔。我们先看一个正常的例子。
SSSSSSSSSSSSSS
TTTTT i=0, j=1,2,3…
TTTTT i=1, j=1,2,3…
TTTTT i=2, j=1,2,3…
我们用T去匹配S，先对齐T和S的头部，然后对比T和S。如果T的范围内，TS内容一致，则匹配成功。不成功的话就将T向后移动一个字符。再次匹配T范围内TS的内容是否一致。ij的范围最大会在0<=i<=“j
KMP算法的核心在于，如果T范围内TS的内容不一致，那么T向后移动不是一个字符，而是多个。而当前比较位置永远不向前移动。如果您写出来的算法当前比较位置向前移动了，那么肯定是写错了。
我们假定T范围内第i个字符匹配失败(0<=i
为什么能移动一个以上呢？Next[i]怎么确定呢？我们看一个抽象的例子：M代表匹配，N不匹配，U不知道。
MMMMMNUUUUU
TTTTTTTTTTTTTTT
TTTTTTTTTTTTTTT
我们可以看到，向后移动字符的时候，T自身有重合的部分。这时候有三种状况，我们先假定一种重合的状况。假定T向后移动了一些字符，P代表当前比较位置。在这个位置上TS出现了不匹配。
..MMMNUUU..
..TTTTTPTTTT..
..MMNTTTTTT..
在这个T向后移动一些距离后，在当前比较位置前已经出现了自身和自身不匹配的状况。根据上面我们知道，当前位置以前的T和S是匹配的。那么就是说，移动了这些字符后。T当前的位置上不可能取得匹配。我们称这种情况为这个位置的自身完全不匹配。
然后是另外一种匹配状况，符号和上面一致。
..MMMNUUU..
..TTTTTPTTTT..
..MMMNTTTT..
这个时候，T在当前匹配位置上自身不匹配，前面位置都匹配。同理可以知道，T在滑移到这个位置后可能取得匹配。我们称这种情况为这个位置的自身部分不匹配。
最后一种匹配情况是。
..MMMNUUU..
..TTTTTPTTTT..
..MMMMUUU..
这个时候，T在在前面和当前位置都匹配。我们知道前面是匹配的，然而当前既然已经被证明了和S不匹配。那么滑移这些位置后，新的位置上T也不可能和S取得匹配。我们称这种情况为这个位置的自身完全匹配。
然后我们可以回头看看比较过程了。当我们对齐TS，然后进行比较的过程中。出现了不匹配。
注意一个问题，我们回朔是为了知道移动后的T是否仍旧匹配。所以如果我们知道T匹配不匹配，就不用回朔。
这个时候我们不移动一次T，然后回朔。而是将T滑移一下，先滑移1位好了。假设出现了当前比较位置的自身完全不匹配或者自身完全匹配，那么滑动1位肯定也无法获得一个有效的匹配。那么就继续滑动，直到出现了自身部分不匹配，或者T已经完全的滑动到了当前位置的后面。这时候T的位置才是有可能获得匹配的位置，其余的位置就没必要浪费时间了。
也就是说，滑移距离Next[i]是i这个位置上滑动距离逐渐增加的时候，首次出现自身部分不匹配情况的位置。如果这情况不出现，那么就设定为<1的值。操作上将整个T滑动到当前位置的后面，并且从下一个位置开始比较起。
然后附上初始版的代码和比较过程。
int *cul_next (char *lpTpl)
{
unsigned int i = 0, j = 0, l = 0;
int *next;
l = strlen (lpTpl);
next = new int[l];
memset (next, 0, l * sizeof (int));
for (i = 1; i < l; i++) {
for (j = 0; j < l - i && lpTpl[j] == lpTpl[j + i]; j++);
if (j < l - i && next[j + i] == 0)
next[j + i] = i;
}
for (i = 0; i < l; i++)
printf ("%dt”, next[i]);
printf (“n”);
return next;
}
int kmp (char *lpSrc, char *lpTpl)
{
char *lpSrc_now = lpSrc;
char *lpTpl_now = lpTpl;
int *next = cul_next (lpTpl);
if (next == NULL)
return -1;
while (*lpSrc_now != ‘’) {
if (*lpSrc_now == *lpTpl_now) {
lpSrc_now++;
lpTpl_now++;
} else {
if (next[lpTpl_now - lpTpl] != 0) {
lpTpl_now -= next[lpTpl_now - lpTpl];
} else {
lpSrc_now++;
lpTpl_now = lpTpl;
}
}
if (*lpTpl_now == ‘’)
break;
printf ("%sn%sn", lpSrc_now, lpTpl_now);
}
delete next;
if (*lpTpl_now != ‘’)
return 0;
return lpSrc_now - lpSrc - strlen (lpTpl);
}
———————————————————————–
0 0 0 0 0 0 0 1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaaaaab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaaaab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaaab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab< br />b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaaab
b
aaa aaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaaab
b
aaaaaaaaaaaaaaab
ab
aaaaaaaaaaaaaab
b
aaaaaaaaaaaaaab
ab
aaaaaaaaaaaaab
b
aaaaaaaaaaaaab
ab
aaaaaaaaaaaab
b
aaaaaaaaaaaab
ab
aaaaaaaaaaab
b
aaaaaaaaaaab
ab
aaaaaaaaaab
b
aaaaaaaaaab
ab
aaaaaaaaab
b
aaaaaaaaab
ab
aaaaaaaab
b
aaaaaaaab
ab
aaaaaaab
b
aaaaaaab
ab
aaaaaab
b
aaaaaab
ab
aaaaab
b
aaaaab
ab
aaaab
b
aaaab
ab
aaab
b
aaab
ab
aab
b
aab
ab
ab
b
ab
ab
b
b
46\