本文共 1577 字，大约阅读时间需要 5 分钟。

题目大意： 给出一个字符串，求出所有 $f[i]$ 的值，$f[i]$ 表示出现次数最多的长度为i的子串的出现次数。

题解

SAM基础题，先求出SAM上每个状态的 $endpos$ 集大小，然后对于每个状态内的最长子串长度 $len$，更新 $f[len]$，其中 $f[i]$ 表示长度为 $i$ 的子串的最大出现次数。

然后再用 $f[i+1$ ~ $n]$ 更新 $f[i]$，因为假如存在长度为 $x$ 的子串出现了 $a$ 次，那么一定也存在长度为 $y(y<x)$ 的子串出现了 $a$ 次，这样就不用担心上面只更新了 $f[len]$ 而没有更新状态内的所有子串长度了。

代码如下：

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define maxn 500010int n;char s[maxn];struct state{
   	int len,link,next[26];}st[maxn];int id=0,last=0,now,p,q;int size[maxn],f[maxn];void extend(int x){
   	now=++id;	st[now].len=st[last].len+1;size[now]=1;	for(p=last;p!=-1&&!st[p].next[x];p=st[p].link)st[p].next[x]=now;	if(p!=-1)	{
   		q=st[p].next[x];		if(st[p].len+1==st[q].len)st[now].link=q;		else		{
   			int clone=++id;			st[clone]=st[q];st[clone].len=st[p].len+1;			for(;p!=-1&&st[p].next[x]==q;p=st[p].link)st[p].next[x]=clone;			st[q].link=st[now].link=clone;		}	}	last=now;}struct edge{
   int y,next;};edge e[maxn];int first[maxn],len=0;void buildroad(int x,int y){
   e[++len]=(edge){
   y,first[x]};first[x]=len;}void dfs(int x){
   	for(int i=first[x];i;i=e[i].next)	dfs(e[i].y),size[x]+=size[e[i].y];	f[st[x].len]=max(f[st[x].len],size[x]);}int main(){
   	scanf("%s",s+1);n=strlen(s+1);	st[0].link=-1;	for(int i=1;i<=n;i++)extend(s[i]-'a');	for(int i=1;i<=id;i++)buildroad(st[i].link,i);	dfs(0);	for(int i=n-1;i>=1;i--)f[i]=max(f[i],f[i+1]);	for(int i=1;i<=n;i++)printf("%d\n",f[i]);}
     
    
   

转载地址：http://xjnib.baihongyu.com/