\(SAM\)\(|Right(A)|\)

\[ |Right(A)|=[Right(A) 存在r=max_A]+\sum |Right(son_A)| \]\(Parent\) 树拓扑即可。

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
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=2001005;
struct node{
node *par,*ch[26];
int _max,id,r_sz;
node(int t1=0,int t2=0,int t3=0){
id=t1; _max=t2; r_sz=t3; par=0; memset(ch,0,sizeof(ch));
}
} *root, *lst, *ad[maxn];
typedef node* P_node;
int n,m,ans[maxn];
char st[maxn];
void Extend(int x){
P_node p=lst, np=new node(++m,p->_max+1,1); ad[m]=np; lst=np;
while(p&&!p->ch[x]) p->ch[x]=np, p=p->par;
if(!p) np->par=root; else{
P_node q=p->ch[x];
if(q->_max==p->_max+1) np->par=q; else{
P_node nq=new node(++m,p->_max+1,0); ad[m]=nq;
while(p&&p->ch[x]==q) p->ch[x]=nq, p=p->par;
memcpy(nq->ch,q->ch,sizeof(q->ch));
nq->par=q->par; q->par=nq; np->par=nq;
}
}
}
queue<int> que;
int d[maxn];
inline void Update_ans(P_node p){
ans[p->_max]=max(ans[p->_max],p->r_sz);
}
int main(){
ad[0]=root=lst=new node(0,0);
scanf("%s",st); n=strlen(st);
for(int i=0;i<=n-1;i++)
Extend(st[i]-'a');
for(int i=1;i<=m;i++) d[ad[i]->par->id]++;
for(int i=1;i<=m;i++) if(!d[i]) que.push(i), ad[i]->r_sz=1, Update_ans(ad[i]);
while(!que.empty()){
int x=que.front(); que.pop();
if(!x) break;
ad[x]->par->r_sz+=ad[x]->r_sz;
int v=ad[x]->par->id;
if((--d[v])==0) que.push(v), Update_ans(ad[v]);
}
for(int i=n-1;i>=1;i--) ans[i]=max(ans[i],ans[i+1]);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}