后缀数组

数据结构与算法
字数统计: 6.6k字   |   阅读时长≈ 35分钟

后缀数组的总结

Step1 - 后缀数组模板+详细注释

1
#include <cstdio>
2
using namespace std;
3
const int MAXN = 100005;
4
//rnk从0开始
5
//sa从1开始,因为最后一个字符(最小的)排在第0位
6
//height从1开始,因为表示的是sa[i - 1]和sa[i]
7
//倍增算法 O(nlogn)
8
int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
9
//Suffix函数的参数m代表字符串中字符的取值范围,是基数排序的一个参数,如果原序列都是字母可以直接取128,如果原序列本身都是整数的话,则m可以取比最大的整数大1的值
10
//待排序的字符串放在r数组中,从r[0]到r[n-1]，长度为n
11
//为了方便比较大小,可以在字符串后面添加一个字符,这个字符没有在前面的字符中出现过,而且比前面的字符都要小
12
//同上,为了函数操作的方便,约定除r[n-1]外所有的r[i]都大于0,r[n-1]=0
13
//函数结束后,结果放在sa数组中,从sa[0]到sa[n-1]
14
void Suffix(int *r, int *sa, int n, int m)
15
{
16
    int i, j, k, *x = wa, *y = wb, *t;
17
    //对长度为1的字符串排序
18
    //一般来说,在字符串的题目中,r的最大值不会很大,所以这里使用了基数排序
19
    //如果r的最大值很大,那么把这段代码改成快速排序
20
    for(i = 0; i < m; ++i) ws_[i] = 0;
21
    for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;//统计字符的个数
22
    for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];//统计不大于字符i的字符个数
23
    for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;//计算字符排名
24
    //基数排序
25
    //x数组保存的值相当于是rank值
26
    for(j = 1, k = 1; k < n; j *= 2, m = k)
27
    {
28
        //j是当前字符串的长度,数组y保存的是对第二关键字排序的结果
29
        //第二关键字排序
30
        for(k = 0, i = n - j; i < n; ++i) y[k++] = i;//第二关键字为0的排在前面
31
        for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;//长度为j的子串sa[i]应该是长度为2 * j的子串sa[i] - j的后缀（第二关键字）,对所有的长度为2 * j的子串根据第二关键字来排序
32
        for(i = 0; i < n; ++i) wv[i] = x[y[i]];//提取第一关键字
33
        //按第一关键字排序 (原理同对长度为1的字符串排序)
34
        for(i = 0; i < m; ++i) ws_[i] = 0;
35
        for(i = 0; i < n; ++i) ws_[wv[i]]++;
36
        for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
37
        for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];//按第一关键字,计算出了长度为2 * j的子串排名情况
38
        //此时数组x是长度为j的子串的排名情况,数组y仍是根据第二关键字排序后的结果
39
        //计算长度为2 * j的子串的排名情况,保存到数组x
40
        t = x;
41
        x = y;
42
        y = t;
43
        for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
44
            x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
45
        //若长度为2 * j的子串sa[i]与sa[i - 1]完全相同,则他们有相同的排名
46
    }
47
}
48
int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
49
void calheight(int *r,int *sa,int n)
50
{
51
    int i,j,k=0;
52
    for(i=1; i<=n; i++)Rank[sa[i]]=i;
53
    for(i=0; i<n; height[Rank[i++]]=k)
54
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
55
}

Step2 - 模板的使用

1
scanf("%s", str);
2
int len = strlen(str);
3
for(i = 0; i < len; i++)
4
{
5
    r[i] = str[i] - 'a' + 1;//将字符串填入r数组
6
}
7
r[i] = 0;//末尾添加一个字符集中没有的树，保证字典序最小，便于编排数组
8
Suffix(r, sa, len + 1, m);//m为字符集大小
9
calheight(r, sa, len);//求 Height 数组

Step3 - 后缀数组的应用

Step3.1 - 最长公共前缀

题目大意：

给定一个字符串，询问某两个后缀的最长公共前缀。

解题思路：

按照上面所说的做法，求两个后缀的最长公共前缀可以转化为求某个区间上 的最小值。对于这个 RMQ 问题（如果对 RMQ 问题不熟悉，请阅读其他相关资料）， 可以用 O(nlogn)的时间先预处理，以后每次回答询问的时间为 O(1)。所以对于 本问题，预处理时间为 O(nlogn)，每次回答询问的时间为 O(1)。如果 RMQ 问题 用 O(n)的时间预处理，那么本问题预处理的时间可以做到 O(n)。

代码：

1
#include <cstdio>
2
#include <cstring>
3
#include <cmath>
4
#include <algorithm>
5
using namespace std;
6
//后缀数组部分
7
const int MAXN = 100005;
8
int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
9
void Suffix(int *r, int *sa, int n, int m)
10
{
11
    int i, j, k, *x = wa, *y = wb, *t;
12
    for(i = 0; i < m; ++i) ws_[i] = 0;
13
    for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;
14
    for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
15
    for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;
16
    for(j = 1, k = 1; k < n; j *= 2, m = k)
17
    {
18
        for(k = 0, i = n - j; i < n; ++i) y[k++] = i;
19
        for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;
20
        for(i = 0; i < n; ++i) wv[i] = x[y[i]];
21
        for(i = 0; i < m; ++i) ws_[i] = 0;
22
        for(i = 0; i < n; ++i) ws_[wv[i]]++;
23
        for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
24
        for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];
25
        t = x;
26
        x = y;
27
        y = t;
28
        for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
29
            x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
30
    }
31
}
32
int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
33
void calheight(int *r,int *sa,int n)
34
{
35
    int i,j,k=0;
36
    for(i=1; i<=n; i++)Rank[sa[i]]=i;
37
    for(i=0; i<n; height[Rank[i++]]=k)
38
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
39
}
40
//RMQ部分
41
int n,minnum[MAXN][17];
42
void RMQ()   		//预处理  O(nlogn)
43
{
44
	int i,j;
45
	int m=(int)(log(n*1.0)/log(2.0));
46
	for(i=1;i<=n;i++)
47
		minnum[i][0]=height[i];
48
	for(j=1;j<=m;j++)
49
		for(i=1;i+(1<<j)-1<=n;i++)
50
			minnum[i][j]=min(minnum[i][j-1],minnum[i+(1<<(j-1))][j-1]);
51
}
52
int ask(int a,int b) 	//O(1)
53
{
54
	int k=int(log(b-a+1.0)/log(2.0));
55
	return min(minnum[a][k],minnum[b-(1<<k)+1][k]);
56
}
57
int askpre(int a,int b)
58
{
59
    a=Rank[a],b=Rank[b];
60
    if(a>b)
61
        swap(a,b);
62
    return ask(a+1,b);
63
}
64
char str[MAXN];
65
int main()
66
{
67
    scanf("%s", str);
68
    n = strlen(str);
69
    int i;
70
    for(i = 0; i < n; i++)
71
    {
72
        r[i] = str[i] - 'a' + 1;
73
    }
74
    r[i] = 0;
75
    Suffix(r, sa, n + 1, 27);
76
    calheight(r, sa, n);
77
    RMQ();
78
    int q;
79
    scanf("%d", &q);
80
    while(q--)
81
    {
82
        int l, r;// 0 <= l <= r < n
83
        scanf("%d %d", &l, &r);
84
        printf("%d\n", askpre(l, r));
85
    }
86
    return 0;
87
}

Step3.2 - 单个字符串的相关问题

这类问题的一个常用做法是先求后缀数组和 height 数组，然后利用 height 数组进行求解。

1. 重复子串

1.1 可重叠最长重复子串

题目大意：

给定一个字符串，求最长重复子串，这两个子串可以重叠。

解题思路：

这道题是后缀数组的一个简单应用。做法比较简单，只需要求 height 数组 里的最大值即可。首先求最长重复子串，等价于求两个后缀的最长公共前缀的最 大值。因为任意两个后缀的最长公共前缀都是 height 数组里某一段的最小值， 那么这个值一定不大于 height 数组里的最大值。所以最长重复子串的长度就是 height 数组里的最大值。这个做法的时间复杂度为 O(n)。

1.2 不可重叠最长重复子串（poj 1743）

题目大意：

给定一个字符串，求最长重复子串，这两个子串不能重叠。

解题思路：

这题比上一题稍复杂一点。先二分答案，把题目变成判定性问题：判断是否 存在两个长度为 k 的子串是相同的，且不重叠。解决这个问题的关键还是利用 height 数组。把排序后的后缀分成若干组，其中每组的后缀之间的 height 值都 不小于 k。例如，字符串为“aabaaaab”，当 k=2 时，后缀分成了 4 组，如图 所示。

img

容易看出，有希望成为最长公共前缀不小于 k 的两个后缀一定在同一组。然 后对于每组后缀，只须判断每个后缀的 sa 值的最大值和最小值之差是否不小于 k。如果有一组满足，则说明存在，否则不存在。整个做法的时间复杂度为 O(nlogn)。本题中利用 height 值对后缀进行分组的方法很常用，请读者认真体 会。

代码（待测）

1
#include <cstring>
2
#include <cstdio>
3
#include <algorithm>
4
#define ll long long
5
using namespace std;
6
const int MAXN = 100005;
7
int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
8
void Suffix(int *r, int *sa, int n, int m)
9
{
10
    int i, j, k, *x = wa, *y = wb, *t;
11
    for(i = 0; i < m; ++i) ws_[i] = 0;
12
    for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;
13
    for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
14
    for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;
15
    for(j = 1, k = 1; k < n; j *= 2, m = k)
16
    {
17
        for(k = 0, i = n - j; i < n; ++i) y[k++] = i;
18
        for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;
19
        for(i = 0; i < n; ++i) wv[i] = x[y[i]];
20
        for(i = 0; i < m; ++i) ws_[i] = 0;
21
        for(i = 0; i < n; ++i) ws_[wv[i]]++;
22
        for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
23
        for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];
24
        t = x;
25
        x = y;
26
        y = t;
27
        for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
28
            x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
29
    }
30
}
31
int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
32
void calheight(int *r,int *sa,int n)
33
{
34
    int i,j,k=0;
35
    for(i=1; i<=n; i++)Rank[sa[i]]=i;
36
    for(i=0; i<n; height[Rank[i++]]=k)
37
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
38
}
39
int n;
40
int check(int k)
41
{
42
    int mx = -0x3f3f3f, mm = 0x3f3f3f;
43
    for(int i = 2; i <= n; i++)
44
    {
45
        if(height[i] >= k)
46
        {
47
            mm = min(mm, min(sa[i], sa[i - 1]));
48
            mx = max(mx, max(sa[i], sa[i - 1]));
49
            if(mx - mm > k)return 1;//如果两个sa相差大于k（等于k不行）则答案可行
50
        }
51
        else
52
        {
53
            mx = -0x3f3f3f, mm = 0x3f3f3f;//重新分组
54
        }
55
    }
56
    return 0;
57
}
58
int main()
59
{
60
    int i;
61
    while(scanf("%d", &n) != EOF)
62
    {
63
        if(n == 0)break;
64
        for(i = 0; i < n; i++)scanf("%d", &r[i]);
65
        n--;
66
        for(i = 0; i < n; i++)r[i] = r[i + 1] - r[i] + 89;//求差值去掉负数
67
        r[i] = 0;
68
        Suffix(r, sa, n + 1, 300);
69
        calheight(r, sa, n);
70
        int l = 0, r = n / 2;
71
        while(l < r)//二分答案
72
        {
73
            int mid = (l + r + 1) / 2;
74
            if(check(mid))l = mid;
75
            else r = mid - 1;
76
        }
77
        if(l >= 4)printf("%d\n", l + 1);//
78
        else printf("0\n");
79
    }
80
    return 0;
81
}

1.3 可重叠的 k 次最长重复子串（poj3261）

题目大意：

给定一个字符串，求至少出现 k 次的最长重复子串，这 k 个子串可以重叠。

解题思路：

这题的做法和上一题差不多，也是先二分答案，然后将后缀分成若干组。不 同的是，这里要判断的是有没有一个组的后缀个数不小于 k。如果有，那么存在 k 个相同的子串满足条件，否则不存在。这个做法的时间复杂度为 O(nlogn)。

代码（待测）

1
#include <cstring>
2
#include <cstdio>
3
#include <algorithm>
4
#define ll long long
5
using namespace std;
6
const int MAXN = 1000005;
7
int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
8
void Suffix(int *r, int *sa, int n, int m)
9
{
10
    int i, j, k, *x = wa, *y = wb, *t;
11
    for(i = 0; i < m; ++i) ws_[i] = 0;
12
    for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;
13
    for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
14
    for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;
15
    for(j = 1, k = 1; k < n; j *= 2, m = k)
16
    {
17
        for(k = 0, i = n - j; i < n; ++i) y[k++] = i;
18
        for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;
19
        for(i = 0; i < n; ++i) wv[i] = x[y[i]];
20
        for(i = 0; i < m; ++i) ws_[i] = 0;
21
        for(i = 0; i < n; ++i) ws_[wv[i]]++;
22
        for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
23
        for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];
24
        t = x;
25
        x = y;
26
        y = t;
27
        for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
28
            x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
29
    }
30
}
31
int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
32
void calheight(int *r,int *sa,int n)
33
{
34
    int i,j,k=0;
35
    for(i=1; i<=n; i++)Rank[sa[i]]=i;
36
    for(i=0; i<n; height[Rank[i++]]=k)
37
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
38
}
39
int n;
40
int check(int k, int x)
41
{
42
    int sum = 1;
43
    for(int i = 2; i <= n; i++)
44
    {
45
        if(height[i] >= k)
46
        {
47
            sum++;
48
        }
49
        else
50
        {
51
            sum = 1;
52
        }
53
        if(sum >= x)return 1;
54
    }
55
    return 0;
56
}
57
int main()
58
{
59
    int i, k;
60
    scanf("%d %d", &n, &k);
61
    for(i = 0; i < n; i++)scanf("%d", &r[i]);
62
    r[i] = 0;
63
    Suffix(r, sa, n + 1, 1000005);
64
    calheight(r, sa, n);
65
    if(k == 1)
66
    {
67
        printf("%d\n", n);
68
    }
69
    else
70
    {
71
        if(k == 2)
72
        {
73
            int ans = 0;
74
            for(i = 1; i <= n; i++)ans = max(ans, height[i]);
75
            printf("%d\n", ans);
76
        }
77
        else
78
        {
79
            int l = 0, r = n;
80
            while(l < r)
81
            {
82
                int mid = (l + r + 1) / 2;
83
                if(check(mid, k))l = mid;
84
                else r = mid - 1;
85
            }
86
            printf("%d\n", l);
87
        }
88
    }
89
    return 0;
90
}

2. 子串的个数

2.1 不相同的子串的个数（spoj694,spoj705）

题目大意：

给定一个字符串，求不相同的子串的个数。

解题思路：

每个子串一定是某个后缀的前缀，那么原问题等价于求所有后缀之间的不相 同的前缀的个数。如果所有的后缀按照 suffix(sa[1]), suffix(sa[2]), suffix(sa[3]), …… ,suffix(sa[n])的顺序计算，不难发现，对于每一次新加 进来的后缀 suffix(sa[k]),它将产生 n-sa[k]+1 个新的前缀。但是其中有 height[k]个是和前面的字符串的前缀是相同的。所以 suffix(sa[k])将“贡献” 出 n-sa[k]+1- height[k]个不同的子串。累加后便是原问题的答案。这个做法 的时间复杂度为 O(n)。

代码：

1
#include <cstring>
2
#include <cstdio>
3
#include <algorithm>
4
#define ll long long
5
using namespace std;
6
const int MAXN = 1000005;
7
int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
8
void Suffix(int *r, int *sa, int n, int m)
9
{
10
    int i, j, k, *x = wa, *y = wb, *t;
11
    for(i = 0; i < m; ++i) ws_[i] = 0;
12
    for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;
13
    for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
14
    for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;
15
    for(j = 1, k = 1; k < n; j *= 2, m = k)
16
    {
17
        for(k = 0, i = n - j; i < n; ++i) y[k++] = i;
18
        for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;
19
        for(i = 0; i < n; ++i) wv[i] = x[y[i]];
20
        for(i = 0; i < m; ++i) ws_[i] = 0;
21
        for(i = 0; i < n; ++i) ws_[wv[i]]++;
22
        for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
23
        for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];
24
        t = x;
25
        x = y;
26
        y = t;
27
        for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
28
            x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
29
    }
30
}
31
int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
32
void calheight(int *r,int *sa,int n)
33
{
34
    int i,j,k=0;
35
    for(i=1; i<=n; i++)Rank[sa[i]]=i;
36
    for(i=0; i<n; height[Rank[i++]]=k)
37
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
38
}
39
int n;
40
char str[MAXN];
41
int main()
42
{
43
    int t, i;
44
    scanf("%d", &t);
45
    while (t--) {
46
        scanf("%s", str);
47
        n = strlen(str);
48
        for(i = 0; i < n; i++)r[i] = str[i];
49
        r[i] = 0;
50
        Suffix(r, sa, n + 1, 300);
51
        calheight(r, sa, n);
52
        ll ans = 0;
53
        for (i = 1; i <= n; i++) ans += n-sa[i]-height[i];
54
        printf("%lld\n", ans);
55
    }
56
    return 0;//
57
}

3. 回文子串

留坑

4. 连续重复字串

4.1 连续重复子串(poj2406)

题目大意：

给定一个字符串 L，已知这个字符串是由某个字符串 S 重复 R 次而得到的， 求 R 的最大值。

解题思路：

做法比较简单，穷举字符串 S 的长度 k，然后判断是否满足。判断的时候， 先看字符串 L 的长度能否被 k 整除，再看 suffix(1)和 suffix(k+1)的最长公共 前缀是否等于 n-k。在询问最长公共前缀的时候，suffix(1)是固定的，所以 RMQ 问题没有必要做所有的预处理，只需求出 height 数组中的每一个数到 height[rank[1]]之间的最小值即可。整个做法的时间复杂度为 O(n)。

也可以使用 KMP 最小循环节解决

代码（待测）

留坑

4.2 重复次数最多的连续重复子串(SPOJ-REPEATS)

题目大意：

给定一个字符串，求重复次数最多的连续重复子串。

解题思路：

先穷举长度 L，然后求长度为 L 的子串最多能连续出现几次。首先连续出现 1 次是肯定可以的，所以这里只考虑至少 2 次的情况。假设在原字符串中连续出 现 2 次，记这个子字符串为 S，那么 S 肯定包括了字符 r[0], r[L], r[L2], r[L3], ……中的某相邻的两个。所以只须看字符 r[Li]和 r[L(i+1)]往前和 往后各能匹配到多远，记这个总长度为 K，那么这里连续出现了 K/L+1 次。最后 看最大值是多少。如图所示。

img

穷举长度 L 的时间是 n，每次计算的时间是 n/L。所以整个做法的时间复杂 度是 O(n/1+n/2+n/3+……+n/n)=O(nlogn)。

代码：

1
#include <cstdio>
2
#include <cmath>
3
#include <cstring>
4
#include <algorithm>
5
using namespace std;
6
const int MAXN = 50005;
7
int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
8
void Suffix(int *r, int *sa, int n, int m)
9
{
10
    int i, j, k, *x = wa, *y = wb, *t;
11
    for(i = 0; i < m; ++i) ws_[i] = 0;
12
    for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;
13
    for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
14
    for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;
15
    for(j = 1, k = 1; k < n; j *= 2, m = k)
16
    {
17
        for(k = 0, i = n - j; i < n; ++i) y[k++] = i;
18
        for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;
19
        for(i = 0; i < n; ++i) wv[i] = x[y[i]];
20
        for(i = 0; i < m; ++i) ws_[i] = 0;
21
        for(i = 0; i < n; ++i) ws_[wv[i]]++;
22
        for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
23
        for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];
24
        t = x;
25
        x = y;
26
        y = t;
27
        for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
28
            x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
29
    }
30
}
31
int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
32
void calheight(int *r,int *sa,int n)
33
{
34
    int i,j,k=0;
35
    for(i=1; i<=n; i++)Rank[sa[i]]=i;
36
    for(i=0; i<n; height[Rank[i++]]=k)
37
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
38
}
39
int n,minnum[MAXN][16];
40
void RMQ()
41
{
42
	int i,j;
43
	int m=(int)(log(n*1.0)/log(2.0));
44
	for(i=1;i<=n;i++)
45
		minnum[i][0]=height[i];
46
	for(j=1;j<=m;j++)
47
		for(i=1;i+(1<<j)-1<=n;i++)
48
			minnum[i][j]=min(minnum[i][j-1],minnum[i+(1<<(j-1))][j-1]);
49
}
50
int Ask_MIN(int a,int b)
51
{
52
	int k=int(log(b-a+1.0)/log(2.0));
53
	return min(minnum[a][k],minnum[b-(1<<k)+1][k]);
54
}
55
int calprefix(int a,int b)
56
{
57
    a=Rank[a],b=Rank[b];
58
    if(a>b)
59
        swap(a,b);
60
    return Ask_MIN(a+1,b);
61
}
62
char s[5];
63
int main()
64
{
65
    int t,i,j,k,ans,Max;
66
    scanf("%d",&t);
67
    while(t--)
68
    {
69
        Max=1;
70
        scanf("%d",&n);
71
        for(i=0;i<n;i++)
72
        {
73
            scanf("%s",s);
74
            r[i]=s[0]-'a'+1;
75
        }
76
        r[i]=0;
77
        Suffix(r,sa,n+1,3);
78
        calheight(r,sa,n);
79
        RMQ();
80
        for(i=1;i<=n;i++)
81
        {
82
            for(j=0;j+i<n;j+=i)
83
            {
84
                ans=calprefix(j,j+i);
85
                k=j-(i-ans%i);
86
                ans=ans/i+1;
87
                if(k>=0&&calprefix(k,k+i)>=i)
88
                    ans++;
89
                Max=max(Max,ans);
90
            }
91
        }
92
        printf("%d\n",Max);
93
    }
94
    return 0;
95
}

Step3.3 - 两个字符串的相关问题

这类问题的一个常用做法是，先连接这两个字符串，然后求后缀数组和 height 数组，再利用 height 数组进行求解。

1. 最长公共字串

题目大意：

给定两个字符串 A 和 B，求最长公共子串。

解题思路：

分隔符将两个字符串连接

后缀数组求height数组后

只要相邻两个分别在两串，就可以用height更新ans

代码：

1
#include <cstring>
2
#include <cstdio>
3
#include <algorithm>
4
#include <iostream>
5
#include <cmath>
6
#define ll long long
7
using namespace std;
8
const int MAXN = 50005;
9
int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
10
void Suffix(int *r, int *sa, int n, int m)
11
{
12
    int i, j, k, *x = wa, *y = wb, *t;
13
    for(i = 0; i < m; ++i) ws_[i] = 0;
14
    for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;
15
    for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
16
    for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;
17
    for(j = 1, k = 1; k < n; j *= 2, m = k)
18
    {
19
        for(k = 0, i = n - j; i < n; ++i) y[k++] = i;
20
        for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;
21
        for(i = 0; i < n; ++i) wv[i] = x[y[i]];
22
        for(i = 0; i < m; ++i) ws_[i] = 0;
23
        for(i = 0; i < n; ++i) ws_[wv[i]]++;
24
        for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
25
        for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];
26
        t = x;
27
        x = y;
28
        y = t;
29
        for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
30
            x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
31
    }
32
}
33
int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
34
void calheight(int *r,int *sa,int n)
35
{
36
    int i,j,k=0;
37
    for(i=1; i<=n; i++)Rank[sa[i]]=i;
38
    for(i=0; i<n; height[Rank[i++]]=k)
39
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
40
}
41
char a[MAXN], b[MAXN];
42
int n;
43
int main()
44
{
45
    int i;
46
    scanf("%s %s", a, b);
47
    int lena = strlen(a);
48
    int lenb = strlen(b);
49
    for(i = 0; i < lena; i++)
50
    {
51
        r[i] = a[i];
52
    }
53
    r[lena] = '#';
54
    for(i = 0; i < lenb; i++)
55
    {
56
        r[i + lena + 1] = b[i];
57
    }
58
    r[lena + lenb + 1] = 0;
59
    Suffix(r, sa, lena + lenb + 2, 300);
60
    calheight(r, sa, lena + lenb + 1);
61
    n = lena + lenb + 1;
62
    int ans = 0;
63
    for(int i = 2; i <= n; i++)
64
    {
65
        int pos1 = sa[i - 1];
66
        int pos2 = sa[i];
67
        if(pos1 <= lena && pos2 <= lena)continue;
68
        else if(pos1 > lena + 1&& pos2 > lena + 1)continue;
69
        else ans = max(ans, height[i]);
70
    }
71
    printf("%d\n", ans);
72
}

2. 子串的个数

留坑

Step3.4 - 多个字符串的相关问题

留坑

  • © 2020 QSH
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信