题目链接:http://codeforces.com/gym/100431/
考虑到对于一个串β,能cover它的最短的α必然是它的border的某个前缀,或者是这个β本身。
所谓border,就是next[len(β)],直观含义是除了串本身以外,使得前缀等于后缀的最长的一段前缀。
发现如果border的两倍就能覆盖整个串,那么问题的规模就减半了,只要求出能cover这个border的最短的串即可。这个关系是具有传递性的,只要border够长,就一直可以推下去。而这种关系可以通过一个last数组实现路径压缩。
如果border的两倍不能覆盖整个串,那就要看border的哪一个前缀可以了,那么哪些前缀可以呢?只有哪些border的border才有可能可以。这是为什么呢?因为只有哪些border的border,才是β串的公共前后缀。那么我们通过一个far数组,维护每一个前缀最远能够覆盖到的位置,动态维护这个数组,通过last数组路径压缩加速即可。
要注意的是far数组的更新要一路更新到底,否则无法把信息维护全。
#include<bits/stdc++.h>
using namespace std; void kmp_pre(char x[],int m,int nxt[])
{
int i,j;
j=nxt[]=-;
i=;
while(i<m)
{
while(-!=j && x[i]!=x[j])j=nxt[j];
nxt[++i]=++j;
}
} const int maxn=;
char s[maxn];
int nxt[maxn];
int last[maxn];
int far[maxn]; int main()
{
freopen("cover.in","r",stdin);
freopen("cover.out","w",stdout);
scanf("%s",s);
int l=strlen(s);
kmp_pre(s,l,nxt);
for (int i=;i<=l;i++) if (nxt[i]*>=i) last[i]=last[nxt[i]]; else last[i]=i;
for (int i=;i<=l;i++)
{
int j=last[i];
far[j]=i;
int now=i;
while (j)
{
if (far[j]>=i-j)
{
now=j;
far[now]=i;
}
j=last[nxt[j]];
}
printf("%d ",now);
}
return ;
}