后缀树 - (sunznx) 振翅飞翔
22 December 2016

后缀树

后缀树,英文名字是 suffix tree,叫后缀的原因是因为后缀是这棵树的重要组成部分,应用场景:字符串匹配,回文。要理解后缀树,首先需要明白字典树的概念,因为后缀树实际上是由字符串的后缀组成的字典树。

例如单词 XMADAMYX 的后缀就有

XMADAMYX
MADAMYX
ADAMYX
DAMYX
AMYX
MYX
YX
X

有了上面这些字符串,我们就可以构造一个字典树。参照 字典树 ,我们用如下的代码来构建

struct node root;

memset(&root, 0, sizeof(root));
root.data = ' ';

insert(&root, "X",        strlen("X"));
insert(&root, "YX",       strlen("YX"));
insert(&root, "MYX",      strlen("MYX"));
insert(&root, "AMYX",     strlen("AMYX"));
insert(&root, "DAMYX",    strlen("DAMYX"));
insert(&root, "ADAMYX",   strlen("ADAMYX"));
insert(&root, "MADAMYX",  strlen("MADAMYX"));
insert(&root, "XMADAMYX", strlen("XMADAMYX"));

生成的字典树就类似下面这样:

根据上图,我们就可以很方便地查出 AMYX 这个串是不是 XMADAMYX 这个串的一部分(字符串匹配)

后缀数组

由于构造字典树的空间成本很高,实际上,我们可以用一个数组来表示这个字符串的所有后缀。如下:

arr[0] = 0;    // 第 0 个字符的后缀,XMADAMYX
arr[1] = 1;    // 第 1 个字符的后缀,MADAMYX
arr[2] = 2;    // 第 2 个字符的后缀,ADAMYX
arr[3] = 3;    // 第 3 个字符的后缀,DAMYX
arr[4] = 4;    // 第 4 个字符的后缀,AMYX
arr[5] = 5;    // 第 5 个字符的后缀,MYX
arr[6] = 6;    // 第 6 个字符的后缀,YX
arr[7] = 7;    // 第 7 个字符的后缀,X

现在,定义一个结构体,来实现真正的后缀数组:

struct suffix {
    int index;
    char *suff;
};

struct suffix suffixes[n];        // n 表示字符串的长度

for (int i = 0; i < n; i++) {
    suffixes[i].index = i;        // 第几个字符串
    suffixes[i].suff  = str + i;  // 后缀串的值
}

构造完后缀数组之后,我们就可以查询一个给定的字符串是不是某个字符串的字串:

int find(suffixes, substr) {
    for (int i = 0; i < n; i++) {
        if (strncmp(suffixes[i].suff, substr, strlen(substr)) == 0) {
            return suffixes[i].index;
        }
    }

    return -1;
}

为了能利用二分查找来实现更快的查找,我们可以对后缀数组进行排序,排序结果存在 SA 上,SA 的结构图如下

代码实现:

int cmp(const void *a, const void *b) {
    return strcmp(((struct suffix *)a)->suff, ((struct suffix *)b)->suff);
}

qsort(tmpSuffixes, n, sizeof(struct suffix), cmp);

for (int i = 0; i < n; i++) {
    SA[i] = tmpSuffixes[i].index;
}

int find(suffixes, SA, substr, l = 0, r = n-1) {
    if (r < l) {
        return -1;
    }

    int m   = (r+l)/2;
    int idx = SA[m];
    int res = strncmp(suffixes[idx].suff, substr, strlen(substr));
    if (res == 0) {
        return idx;
    } else if (res < 0) {         // suff < substr
        return find(suffixes, SA, substr, m+1, r);
    } else {                      // suff > substr
        return find(suffixes, SA, substr, l, m-1);
    }
}

构造 sa 数组还有更搞笑的方法,详见 后缀数组 sa 数组计算,倍增算法

rank 数组

在前面,我们知道,SA 数组是用来表示某个后缀的排名,例如
SA[0]=2 ,表示的是排名是第 0 位的是 下标为 2 的后缀(即 ADAMYX
SA[5]=7 ,表示的是排名是第 5 位的是 下标为 7 的后缀(即 X

那么 rank 数组是什么?
rank[i]=x 表示的是下标为 i 的后缀,他的排名是 x

rank 和 SA 是一个互逆的关系(线性代数有点弱,难以用术语描述 -_-),例如

SA[0] = 2;
SA[5] = 7;

那么就有

rank[2] = 0;
rank[7] = 5;

构造 rank 的代码:

for (int i = 0; i < n; i++) {
   int idx = SA[i];
   rank[idx] = i;
}

应用场景

下面的内容来自 数据结构之——后缀数组

  1. 最长公共前缀
    给定一个串,求任意两个后缀的最长公共前缀。
    解:先根据 rank 确定这两个后缀的排名 i 和 j(i<j),在 height 数组 i+1 和 j 之间寻找最小值。(可以用 rmq 优化)
    (这里为什么是 i+1 呢,因为排名 i 和排名 i+1 的前缀为 height[i+1]
  2. 最长重复子串(不重叠)(poj1743)
    解:二分长度,根据长度 len 将 height 分组,若某组里 SA 的最大值与最小值的差>=len,则说明存在长度为 len 的不重叠的重复子串。
  3. 最长重复子串(可重叠)
    解:height 数组里的最大值。这个问题等价于求两个后缀之间的最长公共前缀。
  4. 至少重复 k 次的最长子串(可重叠)(poj3261)
    解:二分长度,根据长度 len 分组,若某组里的个数>=k,则说明存在长度为 len 的至少重复 k 次子串。
  5. 最长回文子串(ural1297)
    给定一个串,对于它的某个子串,正过来写和反过来写一样,称为回文子串。
    解:枚举每一位,计算以这个位为中心的的最长回文子串(注意串长要分奇数和偶数考虑)。
    将整个字符串反转写在原字符串后面,中间用$分隔。这样把问题转化为求某两个后缀的最长公共前缀。
  6. 最长公共子串(poj2774)
    给定两个字符串 s1 和 s2,求出 s1 和 s2 的最长公共子串。
    解:将 s2 连接到 s1 后,中间用$分隔开。
    这样就转化为求两个后缀的最长公共前缀,注意不是 height 里的最大值,是要满足 sa[i-1]和 sa[i]不能同时属于 s1 或者 s2。
  7. 长度不小于 k 的公共子串的个数(poj3415)
    给定两个字符串 s1 和 s2,求出 s1 和 s2 的长度不小于 k 的公共子串的个数(可以相同)。
    解:将两个字符串连接,中间用$分隔开。扫描一遍,每遇到一个 s2 的后缀就统计与前面的 s1 的后缀能产生多少个长度不小于 k 的公共子串,这里 s1 的后缀需要用单调栈来维护。然后对 s1 也这样做一次。
  8. 至少出现在 k 个串中的最长子串(poj3294)
    给定 n 个字符串,求至少出现在 n 个串中 k 个的最长子串。
    将 n 个字符串连接起来,中间用$分隔开。二分长度,根据长度 len 分组,判断每组的后缀是否出现在不小于 k 个原串中。

相关阅读