寒假学了一下字符串里的后缀数组， 以及入门了后缀自动机。 在此记录。

后缀数组和后缀自动机都是处理字符串问题的有力工具.

后缀数组

推荐看看 这篇文章, 关于后缀数组也基本是从这篇文章学习。

用字符数组s表示字符串: s[i:j]表示字符s[i], s[i+1], … , s[j-1]组成的字符串。len(s)表示字符串长度， s[:j]即s[0:j], s[i:]即s[i:len(s)]。 会Python的都知道我在说啥

子串和后缀的定义: 对于字符串s， 则s[i:j]为s的一个子串。 s[i:]为s的后缀。(s[:j]表示前缀)

字符串的大小关系: 对于两个字符串sa, sb. 分别从串首依次向右比较, 出现第一次 sa[i]<sb[i] . 则sa<sb .若 sa[i]>sb[i] 则 sa>sb, 若 sa[i]==sb[i], 则i++, 继续比较. 若直到 i==len(sa)-1 或 i==len(sb)-1 .仍无法比较出大小, 认定较短的字符串较小.

后缀数组的核心思想就是在O(n logn)/O(n)的时间内对一个字符串的所有后缀进行排序. 并利用排序后的结果处理一些字符串问题.

排序结果的保存: 对于字符串s, 用两个数组sa, rank记录排序结果. sa[i]表示第i小的后缀为s[sa[i]:], rank[i]表示后缀s[i:]为第rank[i]小的后缀.

后缀数组的应用

最长公共前缀

定义height数组: height[i]表示s[sa[i]:]和s[sa[i+1]:]的最长公共前缀。即按照大小排序的后缀中, 相邻两个后缀的公共前缀.

height数组可以在求出sa, rank的前提下在O(n)时间内求出。

考虑height[rank[i]]和height[rank[i+1]].

height[rank[i]]表示后缀s[i:] 和后缀s[sa[rank[i]+1]:]的最长公共前缀x1.

对于后缀s[i+1:], 显然s[sa[rank[i]+1]+1:]的最长公共前缀为x1-1. (之前两个字符串均删除首字符).

故

因此按照该顺序进行计算height数组, 无须每次从头比较, 可以达到O(n)复杂度.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void buildLcp(int *s, int *sa, int *rank, int *lcp, int len)
{
    int n = len;
    for(int i=0; i<=n; i++)
        rank[sa[i]] = i;
    int h = 0;
    lcp[0] = 0;
    for(int i=0; i<n; i++)
    {
        int j = sa[rank[i]-1];
        if(h>0) h--;
        for(; j+h<n && i+h<n; h++)
            if(s[i+h] != s[j+h]) break;
        lcp[rank[i]-1] = h;
    }
    lcp[n] = 105000;
}

求得height数组之后即可知道按后缀大小排序的任意两个相邻后缀的lcp. 对于任意两个后缀s[i:], s[j:], lcp显然为min(height[rank[i]] for i in range(i, j)). (用心感受). 用stRMQ预处理. 即可O(1)查询

POJ3581

给定N个数, a1, a2, …, an. 其中a1比其他数字都大. 把这个序列分成三段, 并将每段分别反转(reverse), 求能得到的字典序最小的序列是什么? (每段不能为空)

N = 5

A = {10, 1, 2, 3, 4} => {10, 1} {2} {3, 4} => {1, 10} {2} {4, 3} => {1, 10, 2, 4, 3}(字典序最小)

由于a1大于其他所有数, 第一段选择逆序之后字典序最小的后缀即可.

an, an-1, [ai, …, a3, a2, a1] , 为什么一定要a1比其他数字都大?

对于j<i, [aj, …, a2, a1]的字典序一定小于[ai, …, a3, a2, a1].

而j>i时, [aj, …, ai, …, a1]在后缀数组中在[ai, …, a2, a1]之后, 是否意味着这一段反转之后一定不如[ai, … a1]优.

考虑[6, 7, 4, 5, 4, 5]: [0,5]在sa中排在[0, 5, 0, 5]之前. 显然选择[0, 5, 0, 5]作为第一部分比选择[0, 5]作为第一部分更优.

第二段和第三段的选择由于不存在如上性质, 不能直接反转之后求后缀数组中排序最小的后缀.

做法: 拼接两次剩余的字符串, 逆序之后求后缀数组. 从最小开始寻找满足条件的即可.

重复子串

  1. 可以重叠的重复子串.

    给定一个字符串, 求最长重复子串, 可以重叠.

    ..height[0]

  2. 不可重叠的最长重复子串

    将问题转化为判定性问题. 二分答案.

    判定是否存在长度为k的, 不重叠的两个子串. 把height数组按照k进行分块. 同一块内height均>=k, 因此同一块内的后缀的公共前缀长至少为k. 若此块内存在任意两个后缀能构成不想交的长为k的子串, 赢了.(这种对height数组分块的做法非常常用)

  3. 可重叠的, 至少出现k次的最长重复子串

    类似于上题, 二分答案, 判定时以k对height进行分块.

子串数目

​ 给一个字符串, 求不相同的子串个数.

​ 字符串的子串与字符串后缀的前缀一一对应.

POJ 2406

​ 还是用kmp做吧…

POJ 3693

​ 给定字符串, 求重复次数最多的连续重复子串.

​ 枚举长度L . 当至少出现2次 时, 在 s[0], s[L], s[2*L], ... 中必然存在两个相邻的字符相同, 利用lcp查找i*L, i*(L+1)的lcp, 再向前查找最长能匹配多少, 就能得到长度为L的周期串最多重复K次. 更新答案.