ShinriiTin/templates/templates/string/kmp

//字符串从0开始
template<size_t size>
struct Kmp{
	int fail[size];
	template<typename T>
	inline void get_fail(T S,int len){
		fail[0]=-1;
		for(int i=1,j;i<len;++i){
			for(j=fail[i-1];~j&&S[j+1]!=S[i];j=fail[j]);
			fail[i]= S[j+1]==S[i]?++j:-1;
		}
	}
	template<typename T>
	inline int match(T A,int lenA,T B,int lenB){
		get_fail(B,lenB);
		int res=0;
		for(int i=0,j=-1;i<lenA;++i){
			while(~j&&B[j+1]!=A[i])j=fail[j];
			if(B[j+1]==A[i])++j;
			if(j==lenB-1)++res,j=fail[j];
		}
		return res;
	}
};

//字符串从1开始
template<size_t size>
struct Kmp{
	int fail[size];
	template<typename T>
	inline void get_fail(T S,int len){
		fail[1]=0;
		for(int i=2,j;i<=len;++i){
			for(j=fail[i-1];j&&S[j+1]!=S[i];j=fail[j]);
			fail[i]= S[j+1]==S[i]?++j:0;
		}
	}
	template<typename T>
	inline int match(T A,int lenA,T B,int lenB){
		get_fail(B,lenB);
		int res=0;
		for(int i=1,j=0;i<=lenA;++i){
			while(j&&B[j+1]!=A[i])j=fail[j];
			if(B[j+1]==A[i])++j;
			if(j==lenB)++res,j=fail[j];
		}
		return res;
	}
};