#define vi vector<int>
vi _kmp(const char *s,int n){//直接传string的话，效率会比较慢s
	vi _ex(n);
	_ex[0]=n;//
	for (int i=1,p=-1,k;i<n;i++)
	{
		if (i<=p) _ex[i]=min(p-i+1,_ex[i-k]);
		while (i+_ex[i]<n && s[i+_ex[i]]==s[_ex[i]]) _ex[i]++;
		if (i+_ex[i]>p) p=i+_ex[i],k=i;
	}
	//for (int i=0;i<n;i++) cout<<_ex[i]<<" ";
	return _ex;
}