扩展kmp

https://blog.csdn.net/discreeter/article/details/52022367
重点在这：
根据extend数组的定义，可以推断出S[po,P]=T[0,P-po],从而得到 S[k+1,P]=T[k-po+1,P-po],令len=next[k-po+1]，(回忆下next数组的定义),分两种情况讨论：

1：k+len<P
2：k+len>=P
int next[N];
int extend[N];
void find_next(string s)
{
	int len = s.length();
	next[0] = len;
	int po = 1,p=0;
	while(s[p]==s[p+1] && p+1<len) 
	p++;
	next[1] = p;
	rep(i,2,len)
	{
		if(next[i-po]+i < next[po]+po)
		next[i] = next[i-po];
		else
		{
			p = next[po]+po-i;
			if(p<0) p=0;
			while(p+i < len && s[p]==s[p+i]) p++;
			next[i] = p;
			po=p;
		}
	}
}
void EXKMP(string s,string p)
{
	find_next(p);
	int po=0,t=0;
	int len1=s.length(),len2=p.length();
	while(s[t]==p[t] && t<len1 && t<len2) t++;
	extend[0]=t;
	rep(i,1,len1)
	{
		if(next[i-po]+i < extend[po]+po)
		next[i]=next[i-po];
		else
		{
			t=extend[po]+po-i;
			if(t<0) t=0;
			while(s[t+i]==p[t]&&t<len2&&t+i<len1) t++;
			po=i;
			extend[i]=t;
		}
	}
}