题意
设 $lcp(s,i,j)$ 在字符串 $s$ 中后缀 $i$ 和 后缀 $j$ 的最长公共前缀。
给一字符串 $s$，对于每个前缀 $s[1,k]$，求 $\mbox{mex}{(lcp(s[1,k],i,j)|1\leq i < j \leq k)}$。
$n\leq 10^6$
题解
若某个 $lcp(i,j)$ 为 $x$，将前面的字符都减少一个，则变为 $x-1$。
因此若集合中有 $x$，则 $1,2,\cdots,x$ 都存在。
显然若集合中有 $0$，则答案为 $\max{(lcp(i,j)|1\leq i < j\leq k)}+1$。
当集合中没有 $0$ 时，任意两个后缀的最长公共前缀均大于等于 $1$，只有字符串中都是一个字母的情况。
除去这种情况后，只需考虑结尾在 $k$ 位的字符串。假设倒序枚举 $j$，使得 $s[1,k]$ 中存在多个 $s[j,k]$。
考虑后缀自动机，若一个字符串所在的节点中，$right$ 集合大小 $\geq 2$ 就可以了。
考虑后缀自动机的性质，$fa[x]$ 的 $right$ 集合大小必定大于 $x$ 的大小，又由于刚加进去的点的 $right$ 集合一定是 $1$，因此 $len[fa[x]]$ 即为所求。
时间复杂度 $O(n)$
程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 2000010
#define S 26
namespace SAM{
int ne[N][S],fa[N],len[N],siz,las;
inline void init()
{
for(int i=0;i<=siz;i++) memset(ne[i],0,sizeof(ne[i])),len[i]=fa[i]=0;
siz=las=1;
}
inline int extend(int c)
{
int cur=++siz,p=las;
len[cur]=len[p]+1;
for(;p&&!ne[p][c];p=fa[p]) ne[p][c]=cur;
if(!p) fa[cur]=1;
else
{
int q=ne[p][c];
if(len[p]+1==len[q]) fa[cur]=q;
else
{
int clone=++siz;
len[clone]=len[p]+1;
fa[clone]=fa[q];
memcpy(ne[clone],ne[q],sizeof(ne[q]));
for(;p&&ne[p][c]==q;p=fa[p]) ne[p][c]=clone;
fa[cur]=fa[q]=clone;
}
}
las=cur;
return len[fa[las]];
}
}
char s[N];
int main()
{
int T,n,ans;
scanf("%d",&T);
for(;T--;)
{
scanf("%s",s);
SAM::init();
n=strlen(s); ans=0;
bool bo=0;
for(int i=0;i<n;i++)
{
if(i) ans=max(ans,SAM::extend(s[i]-'a')+1);
if(s[i]!=s[0]) bo=1;
printf("%d",ans*bo);
printf((i==n-1)?"\n":" ");
}
}
return 0;
}
|