hihocoder 后缀自动机四·重复旋律6

题目

对于\(k\in[1,n]\)求出长度为\(k\)的子串出现次数最多的出现了多少次

我直到现在才理解后缀自动机上的子树和是什么意思

非常显然的一点是

\[endpos(link(u))⊇endpos(u)
\]

考虑到\(link(u)\)有多个儿子

于是还需要\(endpos\)的另外一个性质

\[endpos(u)∩endpos(v)=\varnothing
\]

当且仅当\(u\)不是\(v\)的后缀的时候

显然\(parent\)树上不可能有两个非父子节点的存在后缀关系

把\(link(u)\)的不同儿子的\(|endpos|\)加在一起并不会导致重复

但是就不会漏了吗

会漏的呀,我们非常显然的漏掉了\(link(u)\)自己产生的那个前缀的后缀

但是什么样的节点会有一个自己的独一无二的前缀的后缀呢,非常明显只有那些直接插入到\(SAM\)里的点了

之后我们把\(parent\)树建出来,之后求一下子树和,\(u\)节点的\(sz[u]\)我们对应到\(len[u]\)上去,之后一个后缀最大值就是答案了

代码

#include<cstdio>
#include<cstring>
#define maxn 1000005
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
char S[maxn];
int n,lst=1,cnt=1,num;
struct E{int v,nxt;} e[maxn<<1];
int sz[maxn<<1],fa[maxn<<1],len[maxn<<1],head[maxn<<1],son[maxn<<1][26],beh[maxn];
inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}
void dfs(int x) {for(re int i=head[x];i;i=e[i].nxt) dfs(e[i].v),sz[x]+=sz[e[i].v];}
inline void ins(int c)
{
int f=lst,p=++cnt; lst=p;
len[p]=len[f]+1,sz[p]=1;
while(f&&!son[f][c]) son[f][c]=p,f=fa[f];
if(!f) {fa[p]=1;return;}
int x=son[f][c];
if(len[f]+1==len[x]) {fa[p]=x;return;}
int y=++cnt;
len[y]=len[f]+1,fa[y]=fa[x],fa[x]=fa[p]=y;
for(re int i=0;i<26;i++) son[y][i]=son[x][i];
while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];
}
int main()
{
scanf("%s",S+1),n=strlen(S+1);
for(re int i=1;i<=n;i++) ins(S[i]-'a');
for(re int i=2;i<=cnt;i++) add(fa[i],i);dfs(1);
for(re int i=2;i<=cnt;i++) beh[len[i]]=max(beh[len[i]],sz[i]);
for(re int i=n;i;--i) beh[i]=max(beh[i],beh[i+1]);
for(re int i=1;i<=n;i++) printf("%d\n",beh[i]);
return 0;
}
上一篇:jQuery常用的元素查找方法总结


下一篇:UIStackView before iOS9.0