z function

z.cpp

//http://e-maxx-eng.github.io/string/z-function.html
vector<int> z_alg(string s){
	int n=s.size();
	vector<int> v(n, 0);
	for(int i=1, l=0, r=0;i<n;++i){
		if(i<=r){ // we can use the already calcuated z-value to "init" the v[i]
			v[i]=min(v[i-l], r-i+1);  // I-L  not i-1 
		}
		else{ // i>r trivial bf
			while(i+v[i]<n && s[v[i]]==s[i+v[i]])
				v[i]++;
			if(i+v[i]-1>r){
				r=i+v[i]-1, l=i;
			}
		}
	}
	return v;
}


vector<int> z_alg(string s){
	int n=s.size();
	vector<int> z(n, 0);
	int L=0,R=0;
	for(int i=1;i<n;++i){
		if(i>R){
			L=R=i;
			while(R<n && s[R-L]==s[R]) R++;
			z[i]=R-L; --R;
		}
		else{   // i<=R 代表[0, R-L] has the same string [L, R], so character i-L(後者) is the same as character i(前者)
			if(z[i-L]<R-i+1) z[i]=z[i-L];
			else{ // use "abababa" to verify this case
				L=i;
				while(R<n && s[R-L]==s[R]) R++;
				z[i]=R-L; --R;
			}
			
		}
	}
}