字符串-后缀树和后缀数组详解

唔仄lo咚锵

发布于 2021-12-31 09:25:31

5.1K0

发布于 2021-12-31 09:25:31

文章被收录于专栏：blog(为什么会重名，真的醉了)

文章目录

后缀树

建议先了解一下字典树。

首先理解后缀的概念，后缀(suffix)即从某个位置开始到末尾的一个子串。例如字符串s=aabab ，它的五个后缀为aabab 、abab 、bab 、ab 、b 。

后缀树(suffix tree)就是把所有的后缀子串用字典树的方法建立的一棵树，如图：

其中根节点为空，还可以在叶子节点后用一个’$'符标识结束，从根节点出发就能到达所有的子串情况。

模板：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int trie[maxn][26];
int pos = 1, n;
char s[maxn], t[maxn];
void insert(int idx) { //构建后缀树
    int p = 0; 
    for (int i = idx; i < n; i++) {
        int u = s[i] - 'a';
        if (trie[p][u] == 0)
            trie[p][u] = pos++;
        p = trie[p][u];
    }
}
bool find() {  //查询是否是子串
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int u = s[i] - 'a';
        if (trie[p][u] == 0)
            return false;
        p = trie[p][u];
    }
    return true;
}
int main() {
    scanf("%s%s", s,t);
    n = strlen(s);
    for (int i = 0; i < n; i++) {//枚举起点
        insert(i);
    }
    printf("%s子串", find() ? "是" : "不是");
    return 0;
}

但是不难发现，建树的时间和空间成本都很高。后缀数组和后缀自动机可以看作是对后缀树时间和空间上的优化，通过映射关系避免建树和提高树节点重复利用率。

后缀数组

概念

直接对后缀树构造和编程不太方便，而后缀数组(suffix array)就是更简单的替代方法。

下标i	后缀s[i]	下标j	字典序	后缀数组sa[j]
0	aabab	0	aabab	0
1	abab	1	ab	3
2	bab	2	abab	1
3	ab	3	b	4
4	b	4	bab	2

后缀数组就是字典序对应的后缀下标，即sa (suffix array缩写)数组。比如s[1]=3 ，表示字典序排1的子串，是原来字符串中第3个位置开始的后缀子串，即ab 。

通过后缀数组能方便的解决一些字符串问题，如在母串s 中查找子串t ，只需在sa[] 上做二分搜索，时间复杂度是O(mlogn) ，m子串长度n母串长度，如查找ba ：

#include<bits/stdc++.h>
using namespace std;
string s, t;
int sa[] = { 0,3,1,4,2 }; //设sa[]已求出
int find() {  //t在s中位置
    int l = 0, r = s.size();
    while (r > l + 1) { //字典序里二分
        int mid = (l + r) / 2;
        if (s.compare(sa[mid], t.length(), t) < 0)
            l = mid;  //-1不相等移动左指针
        else r = mid; //0相等移动右指针
    }
    if (s.compare(sa[r], t.length(), t) == 0)
        return sa[r];  //返回原始位置
    if (s.compare(sa[l], t.length(), t) == 0)
        return sa[l];
    return -1; //没找到
}
int main() {
    s = "aabab";
    t = "ba";
    cout << find();
    return 0;
}

sa[]

那现在的问题是如何高效的求后缀数组sa[] ，即对后缀子串进行排序？

若直接使用快排，每两个字符串间还有O(n) 的比较，所以总的复杂度是O(n^2logn) ，显然不够友好。答案是使用倍增法。

用数字替代字母，如a=0，b=1。
连续两个数字组合，如00代表aa，01代表ab，最后一个1没有后续，在尾部加上0，组成10，并不影响字符得比较。
连续4个数字组合，如0010代表aaba，同样得01和10没有后续，补0。
得到5个完全不一样的数字，可以区分大小了，进行排序，得到rk数组={0,2,4,1,3}。
最后通过排名得到后缀数组sa[]={0,3,1,4,2}。

步骤	a	a	b	a	b
第一步	0	0	1	0	1
第二步	00	01	10	01	10
第三步	0010	0101	1010	0100	1000
下标i	0	1	2	3	4
排序rk[i]	0	2	4	1	3
转换sa[i]	sa[0]=0	sa[2]=1	sa[4]=2	sa[1]=3	sa[3]=4
sa[i]	0	3	1	4	2

上述每一步递增两倍，总共log(n) 步，但是当字符串很长时，产生的组合数字就非常大可能溢出，这时就需要每一步都进行一个压缩，只要相对顺序不变即可，如下：

步骤	a	a	b	a	b
第一步	0	0	1	0	1
第二步	00	01	10	01	10
排序rk[]	0	1	2	1	2
第三步	02	11	22	10	20
下标i	0	1	2	3	4
排序rk[i]	0	2	4	1	3
转换sa[i]	sa[0]=0	sa[2]=1	sa[4]=2	sa[1]=3	sa[3]=4
sa[i]	0	3	1	4	2

rk[]

也就是说求后缀数组sa[] ，需要通过一个排名rk[] 来求。两者是一一对应的关系，互为逆运算，可以互相推导，即sa[rk[i]]=i ，rk[sa[i]]=i 。

sa[]后缀数组，suffix array缩写，记录的是位置，是字典序排名第i的是谁。
rk[]排名数组，rank array缩写，记录的是排名，是第i个后缀子串排名第几。

那得到倍增后的相对大小数字后，我们可以直接用快排sort() 得到rk[] ，每次快排O(nlogn) ，需要快排log(n) 次，总复杂度是O(n(logn)^2) 。模板：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200005;
char s[maxn];
int sa[maxn], rk[maxn], tmp[maxn + 1];
int n, k;
bool cmp_sa(int i, int j) { //直接比较，省去组合过程
    if (rk[i] != rk[j]) //比较组合数高位
        return rk[i] < rk[j];
    else { //比较组合数低位
        int ri = i + k <= n ? rk[i + k] : -1;
        int rj = j + k <= n ? rk[j + k] : -1;
        return ri < rj;
    }
}
void calc_sa() { //计算sa[]（快速排序）
    for (int i = 0; i <= n; i++) {
        rk[i] = s[i]; //记录原始数值
        sa[i] = i; //记录当前排序结果
    }
    for (k = 1; k <= n; k *= 2) { //每次递增2倍
        sort(sa, sa + n, cmp_sa);
        //因为rk[]存在相同数，所以需要上一轮rk[]才能比较（即cmp_sa里）
        //所以不能直接赋给rk[]，需要一个tmp[]周转
        tmp[sa[0]] = 0; 
        for (int i = 0; i < n; i++) //sa[]倒推组合数记录在tmp[]
            tmp[sa[i + 1]] = tmp[sa[i]] + (cmp_sa(sa[i], sa[i + 1]) ? 1 : 0);
        for (int i = 0; i < n; i++)
            rk[i] = tmp[i];
    }
}
int main() {
    memcpy(s, "aabab", 6);
    n = strlen(s);
    calc_sa();
    for (int i = 0; i < n; i++)
        cout << sa[i] << " ";
    // 0 3 1 4 2
    return 0;
}

除了直接用快排sort，还有一种更快的排序方式——基数排序，总复杂度只有O(nlogn) ，就是有题目卡这点时间，~~丧心病狂~~。

基数排序是先比较低位再比较高位，使用哈希的思路，对于该位相同的数字直接放到相应的格子里。如排序{82,43,67,52,91,40}，先按个位排序得{40,91,82,52,43,67}，再按十位排序得{40,43,52,67,82,91}以此类推。

格子	0	1	2	3	4	5	6	7	8	9
个位	40	91	82,52	43				67
十位					40,43	52	67		82	91

模板：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200005;
char s[maxn];
int sa[maxn], rk[maxn];
int cnt[maxn], t1[maxn], t2[maxn];
int n, k;
void calc_sa() { //计算sa[](基数排序)
    int m = 127; //ASCLL范围
    int i, * x = t1, * y = t2;
    for (i = 0; i < m; i++)cnt[i] = 0;
    for (i = 0; i < n; i++)cnt[x[i] = s[i]]++;
    for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
    for (i = n - 1; i >= 0; i--)sa[--cnt[x[i]]] = i;
    for (k = 1; k <= n; k *= 2) {
        int p = 0; //利用长度k的排序结果对长度2k的排序
        for (i = n - k; i < n; i++)y[p++] = i;
        for (i = 0; i < n; i++)
            if (sa[i] >= k)y[p++] = sa[i] - k;
        for (i = 0; i < m; i++)cnt[i] = 0;
        for (i = 0; i < n; i++)cnt[x[y[i]]]++;
        for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
        for (i = n - 1; i >= 0; i--)sa[--cnt[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1;
        x[sa[0]] = 0;
        for (i = 1; i < n; 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() {
    memcpy(s, "aabab", 6);
    n = strlen(s);
    calc_sa();
    for (int i = 0; i < n; i++)
        cout << sa[i] << " ";
    // 0 3 1 4 2
    return 0;
}

height[]

height[]是一个辅助数组，和最长公共前缀(Longest Common Prefix，LCP)相关。

定义height[i] 为sa[i-1] 和sa[i] 的最长公共前缀长度。例如前面的aabab 中，sa[1] 表示ab ，sa[2] 表示abab ，那么height[2]=2 。

用暴力的方法比较相邻的sa[] ，复杂度是O(n^2) ，下面给出复杂度为O(n) 的模板：

void getheight(int n) { //n是字符串长度
    int k = 0;
    for (int i = 0; i < n; i++)
        rk[sa[i]] = i;
    for (int i = 0; i < n; i++) {
        if (k)k--;
        int j = sa[rk[i] - 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k])k++;
        height[rk[i]] = k;
    }
}

（~~插播反爬信息~~ ）博主CSDN地址：https://wzlodq.blog.csdn.net/

例题

利用后缀数组可以解决很多字符串解决题目，如：

在串s 中查找子串t 前面给出过代码，二分查找sa[] 即可。
在串s 中找最长重复子串height[] 数组中最大值就是最长重复子串长度，该最长重复子串
找串s1 和串s2 的最长公共子串在合并串s1 和串s2 为串s3 ，并在中间插入一个’$’，这样就转换成了找最大重复子串，但是需要判断对应sa[i] 和sa[i-1] 是否分别属于’$'前后两个字符串。
找串s的最大回文子串一般用Manacher（马拉车）算法。

HDU-1403最长公共子串

HDU-1403 Longest Common Substring

Given two strings, you have to tell the length of the Longest Common Substring of them. For example: str1 = banana str2 = cianaic So the Longest Common Substring is “ana”, and the length is 3. Input The input contains several test cases. Each test case contains two strings, each string will have at most 100000 characters. All the characters are in lower-case. Process to the end of file. Output For each test case, you have to tell the length of the Longest Common Substring of them. Sample Input banana cianaic Sample Output 3

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200005;
char s[maxn];
int sa[maxn], rk[maxn], height[maxn];
int cnt[maxn], t1[maxn], t2[maxn];
int n, k;
void calc_sa() {
    int m = 127;
    int i, * x = t1, * y = t2;
    for (i = 0; i < m; i++)cnt[i] = 0;
    for (i = 0; i < n; i++)cnt[x[i] = s[i]]++;
    for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
    for (i = n - 1; i >= 0; i--)sa[--cnt[x[i]]] = i;
    for (k = 1; k <= n; k *= 2) {
        int p = 0;
        for (i = n - k; i < n; i++)y[p++] = i;
        for (i = 0; i < n; i++)
            if (sa[i] >= k)y[p++] = sa[i] - k;
        for (i = 0; i < m; i++)cnt[i] = 0;
        for (i = 0; i < n; i++)cnt[x[y[i]]]++;
        for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
        for (i = n - 1; i >= 0; i--)sa[--cnt[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1;
        x[sa[0]] = 0;
        for (i = 1; i < n; 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;
    }
}
void getheight(int n) {
    int k = 0;
    for (int i = 0; i < n; i++)
        rk[sa[i]] = i;
    for (int i = 0; i < n; i++) {
        if (k)k--;
        int j = sa[rk[i] - 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k])k++;
        height[rk[i]] = k;
    }
}
int main() {
    while (~scanf("%s", s)) {
        int len1 = strlen(s);
        s[len1] = '$';
        scanf("%s", s + len1 + 1);
        n = strlen(s);
        calc_sa();
        getheight(n);
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (height[i] > ans) {
                if ((sa[i] < len1 && sa[i - 1] >= len1) || sa[i - 1] < len1 && sa[i] >= len1)
                    ans = height[i];
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

这题快排和基数排序差了近十倍的速度。

洛谷P2408 不同子串个数

P2408 不同子串个数

题目背景 因为NOI被虐傻了，蒟蒻的YJQ准备来学习一下字符串，于是它碰到了这样一道题： 题目描述 给你一个长为N的字符串，求不同的子串的个数我们定义两个子串不同，当且仅当有这两个子串长度不一样或者长度一样且有任意一位不一样。子串的定义：原字符串中连续的一段字符组成的字符串 输入格式 第一行一个整数N 接下来一行N个字符表示给出的字符串 输出格式 一行一个整数，表示不一样的子串个数 输入输出样例 输入 #1 5 aabaa 输出 #1 11 输入 #2 3 aba 输出 #2 5 说明/提示 请使用64位整数来进行输出（具体来说，C++和C选手请使用long long 类型，pascal选手请使用Int64）由于输入文件过大，请使用高效的读入方法（具体的，c++和c选手请不要使用cin，pascal选手不需要管）对于30%的数据，N≤1000 对于100%的数据，N≤105

每个后缀sa[i] 产生了n-sa[i] 个前缀，而产生的这些前缀中有height[i] 个是重复的，也就是产生了n-sa[i]-height[i] 个不同子串。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200005;
char s[maxn];
int sa[maxn], rk[maxn], height[maxn];
int cnt[maxn], t1[maxn], t2[maxn];
int n, k;
void calc_sa() {
    int m = 127;
    int i, * x = t1, * y = t2;
    for (i = 0; i < m; i++)cnt[i] = 0;
    for (i = 0; i < n; i++)cnt[x[i] = s[i]]++;
    for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
    for (i = n - 1; i >= 0; i--)sa[--cnt[x[i]]] = i;
    for (k = 1; k <= n; k *= 2) {
        int p = 0;
        for (i = n - k; i < n; i++)y[p++] = i;
        for (i = 0; i < n; i++)
            if (sa[i] >= k)y[p++] = sa[i] - k;
        for (i = 0; i < m; i++)cnt[i] = 0;
        for (i = 0; i < n; i++)cnt[x[y[i]]]++;
        for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
        for (i = n - 1; i >= 0; i--)sa[--cnt[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1;
        x[sa[0]] = 0;
        for (i = 1; i < n; 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;
    }
}
void getheight(int n) {
    int k = 0;
    for (int i = 0; i < n; i++)
        rk[sa[i]] = i;
    for (int i = 0; i < n; i++) {
        if (k)k--;
        int j = sa[rk[i] - 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k])k++;
        height[rk[i]] = k;
    }
}
int main() {
    scanf("%d%s", &n, s);
    n++;
    calc_sa();
    getheight(n);
    n--;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        ans += n - sa[i] - height[i];
    printf("%lld", ans);
    return 0;
}

HDU-5769Substring

HDU-5769 Substring

?? is practicing his program skill, and now he is given a string, he has to calculate the total number of its distinct substrings. But ?? thinks that is too easy, he wants to make this problem more interesting. ?? likes a character X very much, so he wants to know the number of distinct substrings which contains at least one X. However, ?? is unable to solve it, please help him. Input The first line of the input gives the number of test cases T;T test cases follow. Each test case is consist of 2 lines: First line is a character X, and second line is a string S. X is a lowercase letter, and S contains lowercase letters(‘a’-‘z’) only. T<=30 1<=|S|<=10^5 The sum of |S| in all the test cases is no more than 700,000. Output For each test case, output one line containing “Case #x: y”(without quotes), where x is the test case number(starting from 1) and y is the answer you get for that case. Sample Input 2 a abc b bbb Sample Output Case #1: 3 Case #2: 3 Hint In first case, all distinct substrings containing at least one a: a, ab, abc. In second case, all distinct substrings containing at least one b: b, bb, bbb.

把后缀按照字典序排序后，相邻两个后缀的前缀一定是相同的（height数组纪录），那么就不用重复考虑了，记录里每个字母向后最近的目标字符出现的位置，所取前缀至少要包含这个字母。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200005;
char s[maxn];
int sa[maxn], rk[maxn], height[maxn];
int cnt[maxn], t1[maxn], t2[maxn];
int n, k;
void calc_sa() {
    int m = 127;
    int i, * x = t1, * y = t2;
    for (i = 0; i < m; i++)cnt[i] = 0;
    for (i = 0; i < n; i++)cnt[x[i] = s[i]]++;
    for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
    for (i = n - 1; i >= 0; i--)sa[--cnt[x[i]]] = i;
    for (k = 1; k <= n; k *= 2) {
        int p = 0;
        for (i = n - k; i < n; i++)y[p++] = i;
        for (i = 0; i < n; i++)
            if (sa[i] >= k)y[p++] = sa[i] - k;
        for (i = 0; i < m; i++)cnt[i] = 0;
        for (i = 0; i < n; i++)cnt[x[y[i]]]++;
        for (i = 1; i < m; i++)cnt[i] += cnt[i - 1];
        for (i = n - 1; i >= 0; i--)sa[--cnt[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1;
        x[sa[0]] = 0;
        for (i = 1; i < n; 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;
    }
}
void getheight(int n) {
    int k = 0;
    for (int i = 0; i < n; i++)
        rk[sa[i]] = i;
    for (int i = 0; i < n; i++) {
        if (k)k--;
        int j = sa[rk[i] - 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k])k++;
        height[rk[i]] = k;
    }
}
int main() {
    int t;
    scanf("%d", &t);
    for (int cs = 1; cs <= t; cs++) {
        char x[3];
        scanf("%s%s", x, s);
        n = strlen(s);
        n++;
        calc_sa();
        getheight(n);
        n--;
        int nex[maxn];
        int pos = n;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == x[0])pos = i;
            nex[i] = pos;
        }
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += n - max(nex[sa[i]], sa[i] + height[i]);
        }
        printf("Case #%d: %lld\n", cs, ans);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/05/16 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

javascript

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

javascript

登录后参与评论

0 条评论

热度