spoj_nsubstr_sam后缀自动机_算法日常[21/100]

 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
62
63
64
65
66
67
68

#include<bits/stdc++.h>
using namespace std;
const int N=250010;
char s[N];
int r[N<<1],id[N<<1],b[N],F[N];
struct sam{
    // 注意N是题目给的n的两倍,因为节点数最多有2*n-1个
    int p,q,np,nq,cnt,last,a[N<<1][26],l[N<<1],f[N<<1];
    sam(){cnt=0;last=++cnt;}
    void init(){
        cnt=0;last=++cnt;
        memset(a,0,sizeof(a));
        memset(l,0,sizeof(l));
        memset(f,0,sizeof(f));
    }
    void extend(int c){
        p=last;np=last=++cnt;l[np]=l[p]+1;
        while(!a[p][c]&&p)a[p][c]=np,p=f[p];
        if(!p)f[np]=1;
        else{
            q=a[p][c];
            if(l[p]+1==l[q])f[np]=q;
                else{
                    nq=++cnt;l[nq]=l[p]+1;
                    memcpy(a[nq],a[q],sizeof(a[q]));
                    f[nq]=f[q]; f[np]=f[q]=nq;
                    while(a[p][c]==q)a[p][c]=nq,p=f[p];
                }
        }
    }
    void solve(){
        init();
        scanf("%s",s);
        int n=strlen(s);
        for(int i=0;i<n;i++)extend(s[i]-'a');

        // 给主链的right值先+1.因为他们都是叶子节点(从构造算法就可以看出来,虽然这个性质我做了这个题才知道)
        // 源点就是1号节点
        for(int p=1,i=0;i<n;i++) p=a[p][s[i]-'a'],r[p]++;
        // 按照len[x]从小到大基数排序，相当于对SAM图进行拓扑排序(源点也是加入排序的)
        // 第一for先按照长度计数，然后第二for再对长度赋予排名，最后第三for让节点长度排名对应于节点
        // 同长度下，先出现的节点排名大(数值小)-->这个没有多大关系,因为同长度的必定不在同一条拓扑链上
        // 因为从源点出发的每一条链的长度都是递增的
        for(int i=1;i<=cnt;i++) b[l[i]]++;
        // 下面的for的i表示的是长度
        for(int i=1;i<=n;i++) b[i]+=b[i-1];
        for(int i=1;i<=cnt;i++) id[b[l[i]]--]=i;
        // 从后往前for,自底向上更新parent的right大小
        for(int i=cnt;i>=1;i--) r[f[id[i]]]+=r[id[i]];

        // 更新答案
        // 每个节点的endpos集合就是它自己代表的子串在串中出现的次数
        // 然后以这个子串为后缀的更长的串出现的位置通过拓扑排序累加上来了,
        // 存到了r[i]中表示这个节点代表的子串在整个串中所有出现的位置！<==>出现次数
        // 所以r[i]和F[len[i]]用max维护就行了
        for (int i=1;i<=cnt;i++) F[l[i]]=max(F[l[i]],r[i]);
        // 因为长度较短的串的F[i]值有可能是比F[i+1]小的，这样的话最优策略是取i+1长的串的后i长
        // 所以f[i] = max(F[i],F[i+1])
        for (int i=n;i>=1;i--) F[i]=max(F[i],F[i+1]);

        for (int i=1;i<=n;i++) printf("%d\n",F[i]);
    }
} sam;
int T;
int main(){
    sam.solve();
    return 0;
}