[ Z algorithm ] Linear-time pattern matching 線性字串匹配 Z演算法

定義一個字串S的Z function:
    Z(i)=0 如果i=0 or S[i]!=S[0]     否則
    Z(i)=max(所有的k滿足 S[0,k-1]=S[i,i+k-1])
從Z function的定義，假設要在字串A裡面匹配字串B
可以先建構字串S=B+(A和B都沒有的字元)+A的Z function陣列
若Z[i]=lenB則表示在A[i-lenB]有一個完全匹配
這裡提供兩個可以$\ord{N}$時間求出Z function陣列的方法:

	inline void z_alg1(char *s,int len,int *z){
	int l=0,r=0;
	z[0]=len;
	for(int i=1;i<len;++i){
	z[i]=r>i?min(r-i+1,z[z[l]-(r-i+1)]):0;
	while(i+z[i]<len&&s[z[i]]==s[i+z[i]])++z[i];
	if(i+z[i]-1>r)r=i+z[i]-1,l=i;
	}
	}
	inline void z_alg2(char *s,int len,int *z){
	int l=0,r=0;
	z[0]=len;
	for(int i=1;i<len;++i){
	z[i]=i>r?0:(i-l+z[i-l]<z[l]?z[i-l]:r-i+1);
	while(i+z[i]<len&&s[i+z[i]]==s[z[i]])++z[i];
	if(i+z[i]-1>r)r=i+z[i]-1,l=i;
	}
	}

view raw Z.cpp hosted with ❤ by GitHub

對一個特殊構建的數據strlen(s)=10000000其效率平均為
z_alg1:   0.106s
z_alg2:   0.089s
這兩種方法的想法是相同的
我們可以知道第一個方法是較為直觀好寫的，但是運算量較大且調用min函數的效率並不高
但仍在可接受的範圍