后缀数组——强大的字符串处理工具

· · 个人记录

在字符串处理当中，后缀树和后缀数组都是非常有力的工具。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。——摘自《后缀数组——处理字符串的有力工具》（罗穗骞）

前置知识

在学习后缀数组之前，应该了解以下几个定义：

  1. 子串：

字符串s中一段连续的字符称为s的子串

  1. 后缀：

字符串的后缀即为从某个位置i到字符串末尾的特殊子串，记作suf[i]

  1. 字符串的大小：

大部分题目中字符串的大小即为为他们的字典序大小（如果你不知道什么是字典序，请出门左转百度一下）

前方高能，非战斗人员请撤离

  1. 后缀数组sa[]：

后缀数组sa[i]表示将字符串s的所有后缀suf[]按字典序大小排序后，排名第i的后缀在原串的位置

即：suf[sa[i]] <= suf[sa[j]]\ \ (i <= j <= n)

  1. 名词数组rk[]

排名数组rk[i]表示将字符串s的所有后缀suf[]按字典序大小排序后，后缀suf[i]的排名

显然，sa[rk[i]] = rk[sa[i]] = i

  1. 基数排序

具体请看这期洛谷日报

倍增法

求后缀数组通常有两种办法：倍增法和DC3算法。

其中倍增算法时间复杂度为O(nlogn),DC3算法为O(n)。不过由于DC3算法常数较大，实际运行中效率仅仅略优于倍增法，且DC3算法代码量较倍增法较大，所以在考场上倍增法更为常见

那么倍增算法究竟是怎么实现的？

倍增算法的内容简单来说是通过每次利用已经排好序的长度为2^{j - 1}的子串，通过基数排序来求得2^{j}长度的子串的sa[]数组，通过上一次求得的rk[]数组得到新的rk[]数组

注意在排序过程中sa[]和rk[]数组对于两个子串完全相同时处理的方法是不一样的：

而对长度为2^{j}的子串进行基数排序时，由于我们已经有了长度为2^{j - 1}的子串大小关系，所以可以将子串分为长度相同的前后两部分，分别作为基数排序的第一第二关键字

看不懂没关系，可以联系下面具体来看

详细的流程

放代码前先放下宏定义

#define rep(i, a, b) for(register int i = (a); i <= (b); i++)
#define foi(i, a, b) for(register int i = (a); i >= (b); i--)
  1. 最开始要排序的子串长度为一，那么他们的第一关键字大小即为他们的字典序大小，第二关键字大小即为他们的前后顺序。进行基数排序
    sz = 80;//sz表示一共有多少个字符，用来进行基数排序
    rep(i, 1, n) rk[i] = s[i] - '0' + 1, tmp[i] = i;
    //tmp[]即为存储第二关键字的桶
    Qsort();

其中基数排序代码如下：

void Qsort() {
    rep(i, 0, sz) bin[i] = 0;//bin[]为桶
    rep(i, 1, n) bin[rk[i]]++;
    rep(i, 1, sz) bin[i] += bin[i - 1];
    foi(i, n, 1) sa[bin[rk[tmp[i]]]--] = tmp[i];
}
  1. 倍增

倍增长度j，在实际代码实现中，为方便书写，定义j表示上一次排序的子串长度。

for (register int j = 1; j <= n; j <<= 1) {

由于再次进行排序时，我们的第一关键字即为上一次的相应位置子串的排名，而第二关键字为上一次对应位置i+长度j的排名，这就导致以字符串s的后j个子串 （第x个子串在这里表示以s中第x位置上的字符为开头的子串，下同） 没有第二关键字，根据字典序的定义，他们的第二关键字应该被处理为最大

    int p = 0;
    rep(i, n - j + 1, n) tmp[++p] = i;//处理没有第二关键字的后j个子串
    rep(i, 1, n) if (sa[i] > j) tmp[++p] = sa[i] - j;
    //注意第i个子串第二关键字是上一次第i+j个子串的排名
    Qsort();

求出sa[]数组后，下面我们要对rk[]数组进行更新，这时tmp[]已经没有用了，所以我们这里让tmp[]数组表示更新后的rk[]数组的值，暂且然rk[]表示上一次的排名。

因为对相同的子串处理方法不一样，所以我们无法简单使用tmp[sa[i]] = i来进行更新

不过由于不同的地方仅仅是子串相同的情况，所以我们只需要在利用上面的式子时进行特判即可

而两个子串i、k完全相同当且仅当上一次的排名rk[i] == rk[k]\ \ 和\ \ rk[i + j] == rk[k + j]同时成立。因为这样就表示新的两个子串第一第二关键字均相同，它们自然相同

    rep(i, 2, n) {
        int v0 = sa[i - 1], v1 = sa[i], v00 = -1, v01 = -1;
        if (v0 + j <= n) v00 = rk[v0 + j];
        if (v1 + j <= n) v01 = rk[v1 + j];
        if (rk[v0] == rk[v1] && v00 == v01) tmp[sa[i]] = p;
        else tmp[sa[i]] = ++p;
    }
    rep(i, 1, n) rk[i] = tmp[i];//更新rk
    sz = p; if (p == n) break;//两个优化
$if (p == n)\ \ break;$当n个子串一共有n个不同的排名时，再进行下一次排序时的第一关键字两两不同，那么也就与第二关键字无关了。这样就说明后缀的大小关系已经确定了 2. 时间复杂度 倍增复杂度为$logn$，倍增时线性求出了第二关键字和$rk[]$数组，而基数排序由于字符集很小，也相当于线性求出，故时间复杂度为$O(nlogn)

现在我们就得出了sa[]数组和rk[]数组，但是有什么用啊？

height[]数组

对于后缀数组来说，最精髓的地方就是height[]数组了，先介绍几个定义：

  1. 最长公共前缀：lcp(i, j)表示suf[i]和suf[j]的最长公共前缀的长度

  2. 定义LCP(i, j) = lcp(sa[i], sa[j])

关于LCP()有两个显而易见的性质：

这样的话我们就可以仅仅讨论i<j时LCP(i, j)的值

  1. height[]$数组：$height[i]=LCP(i - 1, i)

即排名第i的后缀与排名i-1的后缀的最长公共前缀

  1. h[]$数组：$h[i] = height[rk[i]]

即第i号后缀与排名在它前一位的后缀的最长公共前缀

在这里给出两个性质：

  1. LCP(i, j) = min(height[k])\ \ (i<k\leq j)

也可以写成

LCP(i, j) = min(LCP(i, k), LCP(k, j))\ \ (i<k<j)

严谨的证明可以在百度上查找，这里仅仅叙述我个人的理解：（才不是我懒得写了）

对于suf[sa[i]]（排名第i的后缀，下同）来说，由于按照字典序排名，suf[sa[i + 1]]的第一个字符相比suf[sa[i + 2]]的第一个字符更有可能和suf[sa[i]]的第一个字符相同

而在第一个字符相同时，第二个字符相同的可能性与上述规律一样

例如字符串ababa，排好顺序的后缀为

a
aba
ababa
ba
baba

这样的话，如果LCP(i, i + 1)（这里将LCP的值理解为最长公共前缀）一定大于LCP(i, i + 2)

这样就说明LCP(i, i + 2)是LCP(i, i + 1)的前缀

而LCP(i, i + 1)一定是suf[sa[i]]和suf[sa[i + 1]]的前缀。LCP(i + 1, i + 2)一定是suf[sa[i + 1]]和suf[sa[i + 2]]的前缀

故LCP(i + 1, i + 2)一定是LCP(i, i + 1)的子串

证毕。

  1. h[i] >= h[i - 1] - 1

因为第i号后缀就等于第i-1号后缀去掉第一个字符，还是因为按字典序排序的原因，h[i - 1]（这里和上面一样看做字符串）减去第一个字符后的字符串一定是排名在第i号后缀前一位的后缀的前缀

这样的话h[i]一定包含h[i - 1]减去第一个字符

求height[]方法

通过结论2，我们可以从1~n递推求出h[i]：

  1. 先令k = h[i-1]-1（定义k为递推出的h[i]）

    int j, k = 0;
    rep(i, 1, n) {
        if (k) k--;//步骤一
        j = sa[rk[i] - 1];
        while (s[i + k] == s[j + k]) k++;//步骤2
        height[rk[i]] = k;//别忘了h[i]的定义
    }

整理在一起就是模板了：


void Qsort() {
    rep(i, 0, sz) bin[i] = 0;
    rep(i, 1, n) bin[rk[i]]++;
    rep(i, 1, sz) bin[i] += bin[i - 1];
    foi(i, n, 1) sa[bin[rk[tmp[i]]]--] = tmp[i];
}

void SA() {
    sz = 80;
    rep(i, 1, n) rk[i] = s[i] - '0' + 1, tmp[i] = i;
    Qsort();
    for (register int j = 1; j <= n; j <<= 1) {
        int p = 0;
        rep(i, n - j + 1, n) tmp[++p] = i;
        rep(i, 1, n) if (sa[i] > j) tmp[++p] = sa[i] - j;
        Qsort();
        p = 1; tmp[sa[1]] = 1;
        rep(i, 2, n) {
            int v0 = sa[i - 1], v1 = sa[i], v00 = -1, v01 = -1;
            if (v0 + j <= n) v00 = rk[v0 + j];
            if (v1 + j <= n) v01 = rk[v1 + j];
            if (rk[v0] == rk[v1] && v00 == v01) tmp[sa[i]] = p;
            else tmp[sa[i]] = ++p;
        }
        rep(i, 1, n) rk[i] = tmp[i];
        sz = p; if (p == n) break;
    }
    int j, k = 0;
    rep(i, 1, n) {
        if (k) k--;
        j = sa[rk[i] - 1];
        while (s[i + k] == s[j + k]) k++;
        height[rk[i]] = k;
    }
}

应用

讲了这么半天，后缀数组究竟怎么应用？这里讲解几经典的应用：

  1. 最长公共子串codevs3160

题目大意：给出字符串A,B求A和B的最长公共子串的长度

注意子串的可以理解为后缀的前缀，那么我们可以将A和B链接在一起，求起点在分别在两个字符串的后缀的最长公共前缀的长度的最大值。

唯一的问题是：起点在A中的后缀与起点在B中的后缀的最长公共前缀是由A的后缀与B的前缀组成。

对于上面一种请况，我们可以在AB中间插入A和B中不会出现的字符，保证最长公共前缀前缀不会穿过AB

这样我们从1到n枚举height[i]，如果sa[i]与sa[i - 1]的起点分别两个字符串中，就用height[i]更新答案

主函数如下：

int cmp2(int i, int fi) {
    return (sa[i] > fi && sa[i - 1] < fi)
        || (sa[i - 1] > fi && sa[i] < fi);
}

int main() {
/*  freopen(".in", "r" ,stdin);
    freopen(".out", "w" ,stdout);*/
    scanf("%s", s + 1); n = strlen(s + 1);
    s[n + 1] = '1';
    scanf("%s", s + n + 2);
    int fi = n + 1; n = strlen(s + 1);
    SA(); int ans = 0;
    rep(i, 2, n) ans = max(ans, (cmp2(i, fi) ? height[i] : 0));
    printf("%d", ans);
    return 0;
}

时间复杂度O(nlogn)为求后缀数组的复杂度

  1. 最长不可重叠公共子串POJ1743

题目大意：给定一个序列s，求最长的相似子串的长度，若长度小于5，输出零。其中相似的的子串定义为其中一个子串的每一项都加上同一个数后与另一个子串完全相同

我们对每一项都与它前面一项求差，这样求相似子串就转变为了求公共子串，求差后的公共子串长度为x时，相应的相似子串长度即为x+1。

这里我们可以二分答案k，k表示最长不可重叠公共子串的长度，这样我们只需要判断存不存在长度为k的不可重叠公共子串

我们从1到n按顺序将height分组，使得同一个组里的最长公共前缀均大于k，这样整个组的公共前缀长度大于k

这时，如果组内最靠前的和最靠后的位置相距大于等于k，这就说明可以满足不出现重叠的公共子串长度大于等于k。当然由于本题的特殊性，若前后相距等于k时，在原来的序列中实际上是重叠的，这个自己可以通过画图看出

主函数如下：

int check(int len) {
    int mx = sa[1], mi = sa[1];
    rep(i, 2, n) {
        if (height[i] >= len)
            mx = max(mx, sa[i]), mi = min(mi, sa[i]);
        else mx = mi = sa[i];
        if (mx - mi >= len + 1) return 1;
    }
    return 0;
}

int search(int l, int r) {
    int mid;
    while (l < r) {
        mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l; 
}

int main() {
    while(scanf("%d", &n) == 1 && n != 0) {
        n--;
        rep(i, 0, n) ss[i] = re();
        rep(i, 1, n) s[i] = ss[i] - ss[i - 1];
        SA();
        int ans = search(1, n / 2);
        printf("%d\n", ans < 4 ? 0 : ans + 1);
    }
    return 0;
}
  1. 最长可重叠的至少重复x次子串POJ3261

和第二题一样，二分答案k，表示最长可重叠的至少重复x次子串的长度

从1到n按顺序分组height[]，使得同一个组里的最长公共前缀均大于k

当这个组里一共有x个后缀时，说明这个组里的公共前缀重复了x次

主程序：

int check(int len) {
    int mx = 1, mi = 1;
    rep(i, 2, n) {
        if (height[i] >= len)
            mx = max(mx, i), mi = min(mi, i);
        else mx = mi = i;
        if (mx - mi >= k - 1) return 1;
    }
    return 0;
}

int search(int l, int r) {
    int mid;
    while (l < r) {
        mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
        //printf("%d ", mid);
    }
    return l; 
}

int main() {
    n = re(), k = re();
    rep(i, 1, n) s[i] = re();
    SA();
    printf("%d", search(1, n));
    return 0;
}
  1. 本质不同的子串个数SPOJ705（洛谷）

因为子串就是后缀的前缀，这样本题就变为后缀之间不相同的前缀个数，按排名考虑每一个后缀的前缀对答案的贡献。

这个后缀的长度即为其前缀个数，而重复出现的前缀的数量即为height[]数组在该处的值

若还有其他后缀与该后缀有公共前缀，一定会出现在其前面的后缀时进行的的计算中减去

最后的式子即为 \sum sa[i] - height[i]

主程序：

int main() {
    int T = re();
    while (T--) {
        scanf("%s", s + 1);
        n = strlen(s + 1); int ans = 0;
        SA();
        rep(i, 1, n) ans += (sa[i] - height[i]);
        printf("%d\n", ans);
        rep(i, 1, n) s[i] = '\0';
    }
    return 0;
}

总结

实际上后缀数组更像是一种思想，在做题时要充分利用后缀数组的性质来进行阶梯

完结撒花