https://wenku.baidu.com/view/8e9ebefb0242a8956bece4b3.html 参考了这个ppt 理解起来还是有点费劲的（还是推荐一下这个课件 里面概念和思路给的比较全）

关键点 在extend[1…k]都已经求出来的情况下，求extend[k]。

关键利用s中有一部分和t相等。extend[k+1]的长度<=（s和t相等部分长度时候） extend[k+1]=next[k-a+1];

否者超出的部分要一一匹配并更新，a,p;

上个板子：

#include
#include
#include
#include
#include
#define mt(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const ll mod=1e9+;
ll extend[];
ll Next[];
ll min(ll x,ll y)
{
if(x>y) return y;
return x;
}
void getNext(string t)
{
mt(Next);
ll len=t.length();
Next[]=len;
ll a,p;
a=;
while( a ? (p - i + ) : ;
while(i + j < len && t[i+j] == t[j]) j++; Next[i]=j; a=i; } } } void exkmp(string s,string t) // s->extend t->next
{
getNext(t);
ll a,p;//
ll slen=s.length();
ll tlen=t.length();
a=p=;
ll len=min(s.length(),t.length());
while(p ? (p - i + ) : ;
while( j < tlen && i+j < slen && s[i + j] == t[j]) j++; extend[i]=j; a=i; } } } // 核心 一个起始位置a 一个最远匹配位置p 然后Next 和 extend数组 int main() { string s,t;// s->exkmp t->Next
int Case;
scanf("%d",&Case);
while(Case--)
{
cin>>s>>t;
exkmp(s,t);

}  
return ;  

}