KMP算法

字符串匹配之KMP算法

假设文本是一个长度为n的字符串T，模板是一个长度为m的字符串P，且m<=n。需要求出模板在文本中的所有匹配点i，即满足T[i]=P[0]，T[i+1]=P[1],…,T[m-1]=P[m-1]的非负整数（注意字符串下标从0开始）。
最朴素的算法就是依此判断每个位置是不是一个匹配点。检查匹配点需要O(m)时间，而可能的匹配点有O(n-m)个，所以最坏的时间复杂度为O(m(n-1))。有一个简单优化：在检查匹配点的合法性时只要一个不同就立即停止匹配，换下一个匹配点。但最坏情况还是需要O(m(n-1))时间。
和朴素算法相比，KMP算法的时间效率就强多了。它首先用O(m)的时间对模板进行预处理，然后用O(n)的时间完成匹配。这样的算法复杂度已经是最好的了。
假定在匹配过程中正在比较文本串位置的字符和模板串abbaaba的最后一个字符，发现二者不同（称为失配），这时，朴素算法会把模板串向右移一位，重新比较abbaaba的第一个字符和文本串!!位置的字符。
KMP算法认为，既然!!位置已经比较过一次，就不应该再比一次了。事实上，我们已经知道灰色部分就是abbaab，应该可以利用模板串本身的特性判断出向右移一位一定不是匹配。同理右移两位或三位也不行，但是右移四位是有可能的。这个时候，需要比较处的字符和abbaaba的第三个字符。

图片下方的那条链是一个状态机，其中编号为i的结点表示已经匹配了i个字符。匹配开始时当前状态是0，成功匹配状态加一（表示多匹配了一个字符），而失配时沿着“失配边”走。比如在这个例子中，如果在状态6时失配，应该转移到状态2。为方便起见，这里用next[i]表示状态i失配时应转移到的新状态，特别注意next[0]=0。
KMP算法不难写出：

void KMP(char* T,char* P,int* next){
	int n=strlen(T),m=strlen(P);
	getNext(P);
	int j=0;
	for(int i=0;i<n;i++){
		while(j&&P[j]!=T[i]) j=next[j];//顺着失配边走，直到可以匹配
		if(P[j]==T[i] j++;
		if(j==m) printf("%d\n",i-m+1);
		}
	}

接下来就到了KMP算法的关键，也是它最巧妙的地方。算法的思想是“用自己匹配自己”，根据next[0],next[1],…,next[i-1]递推next[i]，上代码：

void getNext(char* P,char* next){
	int m=strlen(P);
	f[0]=0,f[1]=0;
	for(int i=1;i<m;i++){
		int j=next[i];
		while(j&&P[i]!=P[j] j=next[j];
		next[i+1]=P[i]==P[j]?j+1:0;
		}
	}

字符串ABRACADABRA的状态转移表如图所示：

到此KMP的基本算法就实现完成了。