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

发表于 更新于 分类于 阅读次数：
SAM后缀自动机刷题笔记 spoj_nsubstr_sam后缀自动机_算法日常 有时候状态差，但你不能放弃，因为算法不经历撕心裂肺的思考和试错，是没有生命力的

题目链接

spoj
VJ

2019年9月6日22:46:10VJ挂了…只能在spoj(所以注册了一手)上交先了，明天来补这个链接

题意

给你一个串,求出出现次数最多的长度为i(属于[1,|S|])的字串,输出它的出现次数

题解

  • 每个节点的endpos集合就是它自己代表的子串在串中出现的次数,然后以这个子串为后缀的更长的串出现的位置通过拓扑排序累加上来了,存到了r[i]中表示这个节点代表的子串在整个串中所有出现的位置总个数！<==>节点i代表的字串的出现次数,所以r[i]和F[len[i]]用max维护就行了
  • 然后拓扑排序可以用基数排序来操作，SAM中常用(不用怕，我注释很多)
  • 因为长度较短的串的F[i]值维护出来之后有可能是比F[i+1]小的，这样的话最优策略是取i+1长的串的后i长的串，这样F[i]值能变大，所以f[i] = max(F[i],F[i+1])

AC代码

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;
}

每天一句叨叨

有时候状态差，但你不能放弃，因为算法不经历撕心裂肺的思考和试错，是没有生命力的