后缀数组(SA)

2019/03/03 16:18
阅读数 65

学习了LRJ神犇的代码。orz。

首先真心建议了解下基数排序!!且要有一定的c++程序经验,否则程序很难看懂。

然后对着下面的程序调试(假装你已经会了算法思想)

弄个一个礼拜一下午就能学会了。

该算法基于倍增,然后错位比较,得到二元对并排序。

具体待更。

代码如下:

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define re register
 6 #define rep(i, a, b) for (re int i = a; i <= b; ++i)
 7 #define repd(i, a, b) for (re int i = a; i >= b; --i)
 8 #define For(i, a, b, s) for (re int i = a; i <= b; s)
 9 #define maxx(a, b) a = max(a, b)
10 #define minn(a, b) a = min(a, b)
11 #define LL long long
12 #define INF (1 << 30)
13 
14 inline int read() {
15     int w = 0, f = 1; char c = getchar();
16     while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();
17     while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar();
18     return w * f;
19 }
20 
21 const int maxn = 1e6 + 5;
22 
23 char s[maxn];
24 int t[maxn], t2[maxn], sa[maxn], c[maxn], n;
25 
26 void build_sa(int m) { // m表示字符集大小
27     int *x = t, *y = t2; // 这样写是个技巧,可以快速交换数组(实际上交换了数组地址)
28     rep(i, 0, m-1) c[i] = 0;
29     rep(i, 0, n-1) c[x[i] = s[i]]++;
30     rep(i, 1, m-1) c[i] += c[i-1];
31     repd(i, n-1, 0) sa[--c[x[i]]] = i; // 到这完成了初始字符串的基数排序
32     for (register int k = 1; k <= n; k <<= 1) {
33         int p = 0;
34         rep(i, n-k, n-1) y[p++] = i; 
35         rep(i, 0, n-1) if (sa[i] >= k) y[p++] = sa[i]-k; //这两句完成了第二关键字的排序,而第二关键字为x[i]+k。
36         rep(i, 0, m-1) c[i] = 0;
37         rep(i, 0, n-1) c[x[y[i]]]++;
38         rep(i, 1, m-1) c[i] += c[i-1];
39         repd(i, n-1, 0) sa[--c[x[y[i]]]] = y[i]; // 再完成第一关键字的排序
40         swap(x, y); // 交换数组,原来的y数组(对应后面的x)没有用了
41         p = 1; x[sa[0]] = 0; // 根据原来的x数组(对应为y数组)修改现在的x数组
42         rep(i, 1, n-1)
43             x[sa[i]] = y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k] ? p-1 : p++;
44         if (p == n) return; // 如果所有数两两不同,到目前为止sa一定唯一不变了,退出
45         m = p; // 修改字符集大小
46     }
47 }
48 
49 int main() {
50     scanf("%s", s);
51     n = strlen(s);
52     build_sa((int)'z'+1);
53     rep(i, 0, n-1) printf("%d ", sa[i]+1);
54     return 0;
55 }

 

展开阅读全文
c++
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部