看毛片（KMP）算法简析
看毛片算法又称KMP算法。该算法之所以得名无外乎如下原因。
每当涉及该算法都甚新鲜，极想把玩一番，经过一番琢磨，终于悟透其本质。遂将其束之高阁，数月之后，再相邂逅，新鲜如初，又是一番把玩、醒悟、遗忘，如此循环以至无穷。足见，该算法与看毛片的道理一脉相承。初看新鲜刺激，观摩研究，醒悟不过如此而已。遂撇下而顾其它，数月之后，复习之，依然新鲜激动如故。以致数年。
KMP算法核心在于求匹配失败时模式串的后退数组，大多数都命名为next数组，感觉pre应该更符合直觉。假设在T[i] 和P[j]处失配，j必须是往回退的不可能在向前走。因此要求的后退数组应该这个样子：pre[sizeof(P)]
（1）
T[i] 和P[j]处失配，则找到pre[j]，假设pre[j]=k,意味着P有相同的前缀和后缀，且长度为k,此时在j处失配，自然要回退，退到哪？退到k处。
（2）
咋求pre[j+1]呢？要分两种情况，
a) pre[j]=pre[k], 所以pre[j+1]=k+1=pre[j]+1，中间那个k+1难理解？要知道k是什么意思，k是P[0..j]的相同前缀和后缀长度，此时两个缀的后面各增加了一个相同的字符，所以pre[j+1]自然要在k的基础上+1了；
b) pre[j]!=pre[k]，这就意味着pre[j+1]的相同前缀和后缀不能用pre[j]那一套了。此时，要有递归的思想了，要观察更早的前缀和后缀是否能满足pre[j]=pre[k]，如果找到这个位置则可基于此求出pre[j+1]了。如果一直往前看，一直没发现满足要求的前缀和后缀，咋整？不咋整，说明P[0..j+1]不存在相同的前缀和后缀，此时如果T[i+1]和P[j+1]失配了，P就只能从头开始了。找不到在代码中这样表示pre[0]=-1。
上面基本就是看毛片算法的精髓。还是结合代码来理解吧。程序不会看会的，得写！
int kmp(char *t, char *p) {
int tsize = strlen(t), psize = strlen(p), k=-1, j=0, i=0, *prev = new int[psize];
prev[0] = -1;
while (j < psize-1)
if ( k == -1 || p[k] == p[j] ) prev[++j] = ++k;
else k = prev[k];
i = j =0;
while (i < tsize && j < psize)
if (j == -1 || t[i] == p[j]) {i++;j++;}
else j = prev[j];
if (j == psize) return i - j;
else return -1;
}求后退数组加模式匹配，世界上基本不会有比这更短的KMP了！
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
