字符串模板（后缀数组、后缀自动机、回文树）

Posted on | In

再整理一遍板子

后缀数组

例题cf432D：问对字符串s，对于所有的前缀，当它等于同长度后缀时，这个子串一共在s中出现多少次。

后缀数组求lcp是logn，显然直接二分即可。复杂度nlogn

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+2;
int n,sa[N],rnk[N],height[N];
char s[N];
int st[N][20];
//sa数组表示字典序为i的后缀是谁，rnk数组表示某个后缀的排名(1~n)
void buildSA(int m=128){
    int cnt[N],rnk1[N],rnk2[N],tmpSA[N];    //cnt[i]用来记录rnk小于等于i的子串已经有多少个了，这样可以直接用cnt[rnk[i]]更新sa
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;++i)
        cnt[(int)s[i]]++;
    for(int i=1;i<=m;i++)
        cnt[i]+=cnt[i-1];
    for(int i=1;i<=n;i++)
        rnk[i]=cnt[(int)s[i]];

    for(int l=1;l<n;l<<=1){
        for(int i=1;i<=n;++i){
            rnk1[i]=rnk[i];
            rnk2[i]=(i+l<=n?rnk[i+l]:0); //如有缺失，名次按0算，即较短的占优势，它和较长的比较时缺失部分的优先级按最高算
        }
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;++i)
            cnt[rnk2[i]]++;
        for(int i=1;i<=n;++i)    //小于等于当前rnk的共有几个后缀
            cnt[i]+=cnt[i-1];
        for(int i=n;i;--i)         //tmpSA这里按rnk2名次记录的后缀
            tmpSA[cnt[rnk2[i]]--]=i;    //--是为了区分rnk相同的串，后访问的排序靠前一些
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;++i)
            cnt[rnk1[i]]++;
        for(int i=1;i<=n;++i)
            cnt[i]+=cnt[i-1];
        for(int i=n;i;--i)
            sa[cnt[rnk1[tmpSA[i]]]--]=tmpSA[i];    //是按照tmpSA的逆序计算，也就是rnk2较大的对应的cnt值会大一些，排在rnk1相同而rnk2较小的后面
        //cnt代表每个桶的大小
        bool uniq=true;     //如果构建完rnk数组还是true，说明所有后缀的大小已经区分出来了，没有排名相同的后缀了，可以退出
        rnk[sa[1]]=1;       //构建新的rank数组
        for(int i=2;i<=n;++i){
            rnk[sa[i]]=rnk[sa[i-1]];
            if(rnk1[sa[i]]==rnk1[sa[i-1]]&&rnk2[sa[i]]==rnk2[sa[i-1]])
                uniq=false;     //这里不能break，因为还要继续把当前rank数组算完
            else
                rnk[sa[i]]++;
        }
        if(uniq)
            break;
    }
}
//height[i]表示位于sa[i-1]和sa[i]的两个后缀的最长前缀
//有性质height[rnk[i]]>=height[rnk[i-1]]-1，即字符串向后推一位，height值最多减小1
void getHeight() {
    for(int i=1,k=0;i<=n;++i){
        if(k) --k;        //新的长度不会比k-1小，是结论
        int j=sa[rnk[i]-1]; //j是排序刚好比i小1的后缀
        while(s[i+k]==s[j+k])
            k++;
        height[rnk[i]]=k;
    }
}

//满足lcp(l,r)=min{height[i+1],...height[r]}，故是RMQ问题
//st[i][j]表示[i,i+(1<<j)-1]的最小height，[i,i+(1<<j)]的lcp，这一点注意一下
void initST(){    //用ST表进行RMQ
    for(int i=1;i<n;i++)
        st[i][0]=height[i+1];
    for(int l=1;(1<<l)<=n-1;l++){
        for(int i=1;i+(1<<l)-1<=n;i++)
            st[i][l]=min(st[i][l-1],st[i+(1<<(l-1))][l-1]);
    }
}

//lcp：最长公共前缀，此处指sa[l]和sa[r]的最长公共前缀
int lcp(int l,int r){
    if(l==r)
        return n-sa[l]+1;
    if(l>r)
        swap(l,r);
    int k=0;
    while((1<<(k+1))+1<=r-l+1) ++k;
    return min(st[l][k],st[r-(1<<k)][k]);
}
vector<pair<int,int>> ans;
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    buildSA();
    getHeight();
    initST();
    for(int len=1;len<=n;len++){
        int a=rnk[1],b=rnk[n-len+1];
        if(lcp(a,b)<len)
            continue;
        if(a>b) swap(a,b);
        int res=b-a+1;
        int l=1,r=a;
        while(l<=r){
            int mid=(l+r)/2;
            if(lcp(mid,a)>=len)
                r=mid-1;
            else
                l=mid+1;
        }
        res+=max(a-l,0);
        l=b,r=n;
        while(l<=r){
            int mid=(l+r)/2;
            if(lcp(mid,b)>=len)
                l=mid+1;
            else
                r=mid-1;
        }
        res+=max(r-b,0);
        ans.push_back(make_pair(len,res));
        //printf("%d %d\n",len,res);
    }
    cout<<ans.size()<<endl;
    for(auto p:ans)
        cout<<p.first<<' '<<p.second<<endl;
    return 0;
}