参考https://www.luogu.org/problemnew/solution/P5410
题目描述
有两个字符串aa,bb,要求输出bb与aa的每一个后缀的最长公共前缀
输入格式
两行,分别为两个字符串aa,bb
输出格式
共两行
第一行有lenb个数,为b的next数组(特别地,next 0为lenb)
第二行有lena个数,即答案
输入输出样例
输入
aaaabaa
aaaaa
输出
5 4 3 2 1
4 3 2 1 0 2 1
代码
#include <stdio.h>
#include <string.h>
#define max(a,b) a>b?a:b
#define maxn 100010
char a[maxn],b[maxn];
int next[maxn],exnext[maxn];
int lena,lenb;
void get_next()
{
next[0]=lenb;
int j=0;
while(j+1<lenb&&b[j+1]==b[j])
j++;
next[1]=j;
int p0=1;
for(int i=2;i<lenb;i++)
{
if(i+next[i-p0]<next[p0]+p0)
next[i]=next[i-p0];
else
{
int now=p0+next[p0]-i;
now=max(now,0);
while(now+i<lenb&&b[now]==b[now+i])
now++;
next[i]=now;
p0=i;
}
}
}
void solve()
{
int j=0;
while(j<lena&&j<lenb&&a[j]==b[j])
j++;
exnext[0]=j;
int p0=0;
for(int i=1;i<lena;i++)
{
if(i+next[i-p0]<exnext[p0]+p0)
{
exnext[i]=next[i-p0];
}
else
{
int now=p0+exnext[p0]-i;
now=max(now,0);
while(now+i<lena&&now<lenb&&a[now+i]==b[now])
now++;
exnext[i]=now;
p0=i;
}
}
}
int main()
{
scanf("%s%s",a,b);
lena=strlen(a),lenb=strlen(b);
get_next();
solve();
for(int i=0;i<lenb;i++)
printf("%d%c",next[i],i!=(lenb-1)?' ':'\n');
for(int i=0;i<lena;i++)
printf("%d ",exnext[i]);
}
