后缀数组

ACM

后缀数组的原理很好懂，但是蓝书上写的代码，我是真的读不懂啊emmmmmmm

后缀数组的原理

运用了倍增的思想，不断的计算后缀的字典序的大小，关于倍增的图可以看刘汝佳那本书上面的图。
我主要画了一下关于最长公共前缀的原理图。

代码里面的说明

其实sa[], x[]两个表示的东西非常的相似：
sa[i]表示的是：后缀的字典序排在第i位在原来的字符串中的位置为sa[i].
x[i]表示的是：字符串中的位置i在字典序中的大小为x[i].
两者其实是map 的值发生了交换。

其中的一段代码看了好久：

1
2
3
4
5
6
//后面的字符串连接的是0，因此优先级最高，更新后面的第二维
for(int i=n-k; i<n; i++){
    y[p++] = i;
}
//更新前面的第二维，有的字母不能影响前面的第二维，判断条件是sa[i]>=k,小于就相当于不能影响前面
for(int i=0; i<n; i++)if(sa[i]>=k) y[p++] = sa[i]-k;

先更新的是后面连接’0’的第二维值，然后更新的是后面影响前面的第二维值。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
string s;
//一个字符串的末尾必须是0，使得它的优先级最大
//x[]是第一维，y[]是第二维的数字
//c[]是统计字符的个数的
int sa[maxn], x[maxn], y[maxn], c[maxn], n;
void build_sa(int m){
    int i;
    for(int i=0; i<m; i++) c[i] = 0;
    //处理原来的字符串，使其范围为0~m-1，并且最后一个字符必须为0.
    for(int i=0; i<n; i++) if(s[i]>='A'&&s[i]<='z')c[x[i]=(s[i]-'A'+1)]++;
                            else {c[0]++; x[i] = 0;}
    for(int i=1; i<m; i++) c[i] += c[i-1];
    for(int i=n-1; i>=0; i--) sa[--c[x[i]]] = i;
    for(int k=1; k<=n; k<<=1){
        int p = 0;
        //后面的字符串连接的是0，因此优先级最高，更新后面的第二维
        for(int i=n-k; i<n; i++){
            y[p++] = i;
        }
        //更新前面的第二维，有的字母不能影响前面的第二维，判断条件是sa[i]>=k,小于就相当于不能影响前面
        for(int i=0; i<n; i++)if(sa[i]>=k) y[p++] = sa[i]-k;
        
        //更新sa[]数组
        for(int i=0; i<m; i++) c[i] = 0;
        for(int i=0; i<n; i++) c[x[y[i]]]++;
        for(int i=1; i<m; i++) c[i] += c[i-1];
        for(int i=n-1; i>=0; i--){
            sa[--c[x[y[i]]]] = y[i];
        }
        swap(x, y);
        p = 1; x[sa[0]] = 0;
        for(int i=1; i<n; i++){
            //若第一维和第二维的数字相等，那么它们的x[]的值是一样的，因为x[i]表示的以i为序号的后缀的排行大小为x[i]
            x[sa[i]] = y[sa[i-1]]==y[sa[i]]&&
            y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
        }
        //顺序全部不等，必然可以排序了
        if(p>=n) break;
        m = p;
    }
}
int main()
{
    s = "BANANA0";
    n = s.length();
    build_sa(255);
    for(int i=0; i<n; i++){
        cout<<sa[i]<<" ";
    }
    cout<<endl;
    return 0;
}

未解决的问题

本文标题:后缀数组

文章作者:Babydragon

发布时间:2018-03-14, 20:11:15

最后更新:2018-03-23, 13:30:21

原始链接:http://baolintian.github.io/2018/03/14/后缀数组/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 后缀数组的原理
  2. 2. 代码里面的说明
  3. 3. 代码
  4. 4. 未解决的问题
{{ live2d() }}