题目

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

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

非常显然的一点是

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

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

当且仅当\(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;

}