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(suffixes, n, sizeof(struct suffix), cmp);

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

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

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

至此,用后缀数组来查找 一个字符串 是否在另一个字符串中已经结束,接下来我们来看看后缀数组的其他应用

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;
}

height 数组

height 数组就是排序后的两个相邻后缀的最长公共前缀长度是多少

这次,我们使用新的字符串 abaab 来测试,首先来看看 SA 数组 和 rank 数组

在 SA 数组里面,我们可以看出

height[a] = 2  (abaab 和 ab)
height[b] = 1  (baab 和 b)
height[a] = 0  (第一个默认为 0)
height[a] = 1  (ab 和 aab)
height[b] = 0  (b 和 abaab)

构造 height 数组的代码(一种不好的实现 -_-,另外需要注意的是这个实现不是按照字符串顺序来的)

for (int i = 0; i < n; i++) {
    height[i] = 0;

    if (i == 0) { continue; }

    int idx1 = SA[i-1];
    int idx2 = SA[i];

    while (idx1 < n && idx2 < n && str[idx1] == str[idx2]) {
        height[i]++;
        idx1++;
        idx2++;
    }
}

上面的做法的缺点是没有利用好字符串的特性,接下来看另外一种实现 O(n)

 1: int k = 0;
 2: 
 3: for (int i = 0; i < n; i++) {
 4:     height[i] = 0;
 5: 
 6:     if (i == 0) { continue; }
 7: 
 8:     if (k > 0) {
 9:         k = k - 1;
10:     } else {
11:         k = 0;
12:     }
13: 
14:     int j = SA[rank[i]-1];
15: 
16:     while (i+k < n && j+k < n && str[i+k] == str[j+k]) {
17:         k++;
18:     }
19: 
20:     height[i] = k;
21: }

上面这段代码对我来说极其烧脑,看了好久才看明白…

要知道

SA[rank[i]] == i
rank[i]            表示 第 i 个 字符的排名是多少
rank[i]-1          表示 排在 i 之前的那个字符串的排名是多少
SA[rank[i]-1]      表示 排名为 rank[i]-1 的 index 是多少

请记住,rank 是排名,SA 是下标

比如

i = 0
-->  {rank[i] = 2,   SA[rank[i]] = 0}
-->  {rank[i]-1 = 1, SA[rank[i]-1] = 3}

这里的 SA[rank[i]]   对应的字符串是 abaab
这里的 SA[rank[i]-1] 对应的字符串是 ab

默认 k 为 0,接着再根据 第 16 行的 while 循环 ,计算出公共前缀是 2。

接下来是 i=1 的计算,下面是重点

i = 1
-->  {rank[i] = 4,   SA[rank[i]] = 0}
-->  {rank[i]-1 = 3, SA[rank[i]-1] = 4}

这里的 SA[rank[i]]   对应的字符串是 baab
这里的 SA[rank[i]-1] 对应的字符串是 b

重点来了,因为我们在前面已经计算过 abaab 这个字符串的公共前缀是 2,对于 baab 这个字符串来说, baab 的前缀最少也是 1(即 k-1) (数学能力比较差,无法解释这个逻辑..)

应用场景

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

  1. 最长公共前缀
    给定一个串,求任意两个后缀的最长公共前缀。
    解:先根据 rank 确定这两个后缀的排名 i 和 j(i<j),在 height 数组 i+1 和 j 之间寻找最小值。(可以用 rmq 优化)
  2. 最长重复子串(不重叠)(poj1743)
    解:二分长度,根据长度 len 分组,若某组里 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 个原串中。

相关阅读