[ Knuth-Morris-Pratt Algorithm ] 克努斯-莫里斯-普拉特(KMP)算法

這是一個大家很常聽到的字串匹配演算法，較Z Algorithm複雜，但更為通用，C++的string就有內建(string::find)。假設要以B匹配A，則會先建立B的部分匹配表(又叫做失配函數)，其定義如下:
     fail(i)=max(滿足B[0,k]=B[i-k,i]的所有k)
同樣的也可以在線性時間來完成
對於KMP演算法的詳細情況請參考這裡
以下提供fail function陣列及匹配的實作

	/*產生fail function*/
	inline void kmp_fail(char *s,int len,int *fail){
	int id=-1;
	fail[0]=-1;
	for(int i=1;i<len;++i){
	while(~id&&s[id+1]!=s[i])id=fail[id];
	if(s[id+1]==s[i])++id;
	fail[i]=id;
	}
	}
	/*以字串B匹配字串A，傳回匹配成功的數量*/
	inline int kmp_match(char *A,int lenA,char *B,int lenB,int *fail){
	int id=-1,ans=0;
	for(int i=0;i<lenA;++i){
	while(~id&&B[id+1]!=A[i])id=fail[id];
	if(B[id+1]==A[i])++id;
	if(id==lenB-1){/*匹配成功*/
	++ans;
	id=fail[id];
	}
	}
	return ans;
	}

view raw KMP.cpp hosted with ❤ by GitHub