学步园

#include <stdio.h><br /> #include <string.h></p> <p>/*********************************/<br /> * KMP<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span><br /> * 预处理时间：O(m), 运行时间O(n)<br /> * 改进了状态机算法的预处理时间<br /> * 依旧利用后缀最前前缀原理<br /> * 理解有限自动机后理解此算法<br /> /*********************************/</p> <p>const int MAXN=10000;<br /> char T[MAXN],P[MAXN];<br /> int next[MAXN];</p> <p>int m,n;</p> <p>void computePrefixFunction()<br /> {<br /> m=strlen(P)-1;<br /> next[1]=0;<br /> int k=0; // k比q延迟了2个身位<br /> int q;<br /> for(q=2;q<=m;++q)<br /> {<br /> while(k>0&&P[k+1]!=P[q])<br /> {<br /> k=next[k];<br /> }<br /> if(P[k+1]==P[q])<br /> {<br /> k=k+1;<br /> }<br /> next[q]=k;<br /> }<br /> }</p> <p>void kmpMatcher()<br /> {<br /> n=strlen(T)-1;<br /> m=strlen(P)-1;<br /> computePrefixFunction();<br /> int q=0; //q比i延迟了一个身位<br /> int i;<br /> for(i=1;i<=n;++i)<br /> {<br /> while(q>0&&P[q+1]!=T[i])<br /> {<br /> q=next[q];<br /> }<br /> if(P[q+1]==T[i]) //同时解决了q=0或者P[q+1]==T[i]两个问题<br /> {<br /> q=q+1;<br /> }<br /> if(q==m)<br /> {<br /> printf("匹配成功，位置：%d/n",i-m+1);<br /> q=next[q];<br /> }<br /> }<br /> }</p> <p>int main()<br /> {<br /> T[0]=P[0]='z';<br /> scanf("%s%s",T+1,P+1);<br /> kmpMatcher();<br /> return 0;<br /> }<br />

算法的思想是这样的, 如果当前已经匹配了一段, 结果匹配下一个字符的时候失败了,  那么应该将模式串向右移动多少来继续匹配呢?

next数组就是这个作用，什么作用呢？

假设文本串T与模式串P。

P[1...k]与T[]的某一段匹配了, 结果P[k+1]与T[]的下一个字符不相等.

这时候,怎么办?  可以在P[]里找一个P[1...k]的最长前缀,而且这个前缀是P[1...k]的一个后缀,  那么这个后缀一定也与T[]的后半段匹配, 假设这个后缀是P[1...s], 那么现在可以继续判断P[s+1]与T[]下一个字符是否相等, 重复这个过程 .如果相等, 那么i++, s++.

就是这么一回事, 基础一定是有限自动机.