后缀数组及其应用

模板及应用

后缀数组

  • 一些定义:SA[i] 排名为i的后缀位置,rk[i] 第i个后缀的排名,height[i] 排名为i的后缀与及排名为(i-1)的后缀的最长公共前缀(LCP)
  1. 给定一个字符串,询问后缀i到后缀j的最长公共前缀
    • height[rk[i]]到height[rk[j]]的最小值
    • O(nlogn)。需要倍增预处理。
  2. 可重叠最长重复子串
    • height[]最大值
    • O(n)
  3. 不可重叠最长重复子串
    • 二分长度len
    • check时对height进行分组,保证同一组中相邻后缀的LCP不小于len,即height>=len。
    • 如果存在一组,其中最小的sa与最大的sa差值不小于len,则len可行,l=mid;否则r=mid-1。
    • O(nlogn)
  4. 可重叠的至少出现k次最长子串
    • 与3方法相同,不同的是check时判断是否存在一组height个数不小于k
    • O(nlogn)
  5. 不同子串个数
    • 按sa[1],sa[2],sa[3] … 的顺序计算,每次答案累加n-sa[i]+1-height[i]。
    • O(n)
  6. 给定一个字符串,求重复次数最多的连续重复子串
    • 先穷举长度 L,然后求长度为 L 的子串最多能连续出现几次。
    • 首先连续出现1 次是肯定可以的,所以这里只考虑至少 2 次的情况。假设在原字符串中连续出现 2 次,记这个子字符串为 S,那么 S 肯定包括了字符 r[0], r[L], r[L·2],r[L·3], ……中的某相邻的两个。所以只须看字符 r[L·i]和 r[L·(i+1)]往前和往后各能匹配到多远,记这个总长度为 K,那么这里连续出现了 K/L+1 次。最后看最大值是多少。
    • O(nlogn)
  7. 求两个字符串的最长公共子串
    • 将两串拼接起来,中间用一个没有出现过的字符隔开,找到最大的height[i],满足sa[i]和sa[i-1]属于两个不同的字符串。
    • O(|A|+|B|)
  8. 给定n个字符串,求至少出现k在k个字符串中的最长公共子串
    • 将n个字符串拼接起来,中间用没有出现过的字符隔开,求后缀数组。然后二分答案,和问题3一样分组,然后看是否存在一组,其后缀出现在至少k个原串中。
    • O(nlogn)
  9. 给定n个字符串,求在每个字符串中至少出现两次且不重叠的最长子串。
    • 将n个字符串拼接起来,中间用没有出现过的字符隔开,求后缀数组。然后二分答案,再将后缀分组。check的时候看是否有一组后缀在每个原来的字符串中至少出现两次,并且在每个原来的字符串中,后缀的起始位置的最大值与最小值之差不小于当前答案(不重叠)。
    • O(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
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100005;

char ch[N], all[N];
int SA[N], rk[N], height[N], tax[N], tp[N], a[N], n, m;
char str[N];
//rk[i] 第i个后缀的排名; SA[i] 排名为i的后缀位置; height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP
//tax[i] 计数排序辅助数组; tp[i] rank的辅助数组(计数排序中的第二关键字),与SA意义一样。
//a为原串
void RSort() {
//rank第一关键字,tp第二关键字。
for (int i = 0; i <= m; i ++) tax[i] = 0;
for (int i = 1; i <= n; i ++) tax[rk[tp[i]]] ++;
for (int i = 1; i <= m; i ++) tax[i] += tax[i-1];
for (int i = n; i >= 1; i --) SA[tax[rk[tp[i]]] --] = tp[i]; //确保满足第一关键字的同时,再满足第二关键字的要求
} //计数排序,把新的二元组排序。

int cmp(int *f, int x, int y, int w) { return f[x] == f[y] && f[x + w] == f[y + w]; }
//通过二元组两个下标的比较,确定两个子串是否相同

void Suffix() {
//SA
for (int i = 1; i <= n; i ++) rk[i] = a[i], tp[i] = i;
m = 127 ,RSort(); //一开始是以单个字符为单位,所以(m = 127)

for (int w = 1, p = 1, i; p < n; w += w, m = p) { //把子串长度翻倍,更新rank

//w 当前一个子串的长度; m 当前离散后的排名种类数
//当前的tp(第二关键字)可直接由上一次的SA的得到
for (p = 0, i = n - w + 1; i <= n; i ++) tp[++ p] = i; //长度越界,第二关键字为0
for (i = 1; i <= n; i ++) if (SA[i] > w) tp[++ p] = SA[i] - w;

//更新SA值,并用tp暂时存下上一轮的rank(用于cmp比较)
RSort(), swap(rk, tp), rk[SA[1]] = p = 1;

//用已经完成的SA来更新与它互逆的rank,并离散rank
for (i = 2; i <= n; i ++) rk[SA[i]] = cmp(tp, SA[i], SA[i - 1], w) ? p : ++ p;
}
//离散:把相等的字符串的rank设为相同。
//LCP
int j, k = 0;
for(int i = 1; i <= n; height[rk[i ++]] = k)
for( k = k ? k - 1 : k, j = SA[rk[i] - 1]; a[i + k] == a[j + k]; ++ k);
//这个知道原理后就比较好理解程序
}

void Init() {
scanf("%s", str);
n = strlen(str);
for (int i = 0; i < n; i ++) a[i + 1] = str[i];
}

int main() {
Init();
Suffix();

int ans = height[2];
for (int i = 3; i <= n; i ++) ans += max(height[i] - height[i - 1], 0);
printf("%d\n", ans);
}

Stammering Aliens

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

bool check(int len){
int sum = 1;
for(int i=2;i<=n;i++){
if(height[i]>=len) sum++;
else sum=1;
if(sum>=num) return true;
}
return false;
}
int main() {
while(~scanf("%d",&num) && num){
Init();
Suffix();
if(num==1){
printf("%d 0\n",n);
continue;
}
int l=0, r=50000, flag=0;
while(l<r){
int mid = l+r+1>>1;
if(check(mid)) l = mid, flag=1;
else r = mid-1;
}
//最长串最后一次出现的位置
int res = 1, sum=1, mx=sa[1];
for(int i=2;i<=n;i++){
if(height[i]>=l) sum++, mx=max(mx,sa[i]);
else sum=1, mx=sa[i];
if(sum>=num) res = max(res,mx);
}
if(flag)printf("%d %d\n", l, res-1);
else puts("none");
}
return 0;
}
Donate comment here