时间限制：1 秒

内存限制：128 兆

题目描述：

给定两个字符串，求它们前后重叠的最长子串的长度，比如"abcde"和“cdefg”是"cde"，长度为3。

 

输入：

输入可能包含多个测试案例。
对于每个测试案例只有一行， 包含两个字符串。字符串长度不超过1000000，仅包含字符‘a‘-‘z‘。

 

输出：

对应每个测试案例，输出它们前后重叠的最长子串的长度。

 

样例输入：

abcde cdefg

样例输出：

3
扩展kmp

#include<cstdio>#include<cstring>#include<algorithm>#define N 1000001using namespace std;char s[N],t[N];int lens,lent,len;int nxt[N],extend[N];void getnxtt(){    int a=0;    nxt[0]=lent;    while(a<lent-1 && t[a]==t[a+1]) a++;    nxt[1]=a;    int p,l,j;    a=1;    for(int k=2;k<lent;k++)    {        p=a+nxt[a]-1,l=nxt[k-a];        if(k-1+l>=p)        {            j=(p-k+1>0) ? p-k+1 : 0;            while(k+j<lent && t[k+j]==t[j]) j++;            nxt[k]=j;            a=k;        }         else nxt[k]=l;    }}void getextend(){    int a=0,len=min(lens,lent);    while(a<len && s[a]==t[a]) a++;    extend[0]=a;    a=0;    int p,l,j;    for(int i=1;i<lens;i++)    {        p=a+extend[a]-1; l=nxt[i-a];        if(i-1+l>=p)        {            j=(p-i+1>0) ? p-i+1 : 0;            while(i+j<lens && j<lent && s[i+j]==t[j]) j++;            extend[i]=j;            a=i;        }        else extend[i]=l;    }}int main(){    while(scanf("%s%s",s,t)!=EOF)    {        bool ok=false;        lens=strlen(s);        lent=strlen(t);        getnxtt();        getextend();        for(int i=0;i<lens;i++)         if(extend[i]==lens-i)          {             printf("%d\n",extend[i]);             ok=true;            break;         }        if(!ok) puts("0");        }}