算法课读书笔记之字符串算法学习体会及其应用-后缀数组

后缀数组 [^3]

一点题外话

好久之前就想学习后缀数组相关算法,但是苦于自己的基础知识不够扎实,而且这个算法对初学者来说难度过高。要大致理解其中的思想其实不难,但是要进行代码实现需要花很大的功夫去理解,静下心来参透每一步的细节。借着这次读书笔记作业的任务，我花了一天的时间对资料进行整理,对代码进行逐行理解和测试,终于对后缀数组的算法有一定的理解了。

后缀数组的实现

首先引入一些定义:

子串: 在字符串 s 中, 任取 i, j(i <= j) 截取字符串 s 从 i 到 j 的一段称为 s 的子串
后缀: 字符串 s 从某个位置 i 开始到末尾的子串, 称为 s 的一个后缀，定义第 i 个字符开头的后缀为suffix(i)
后缀数组: 把 s 的每一个后缀进行字典序排序, sa[i] 表示排名为 i 的后缀的起始位置
rank[i]: 起始位置为 i 的后缀的排名, 它和 sa[i] 满足 $rank = sa^{-1}，即 sa[i] = j, rank[j] = i$

那么我们要怎么得到后缀数组呢?如果考虑普通的快速排序对每个后缀进行排序的话,我们知道字符串大小之间的比较时间复杂度是 $O(n)$ 的,那么总的时间复杂度就是 $O(n^2logn)$ 显然这个时间复杂度不是很优秀,我们需要一种更高效的方法去优化这个问题。

方法1. DA(doubling algorithm）算法

倍增法的基本思想是,计算 t 的所有位置处长度为2的幂次的前缀的秩, 长度为2h的前缀的秩可以根据长度为 h 的前缀的秩,并利用基数排序算法计算.
这里需要引入一个定理: 对于 s 的所有后缀 $S_{i}$ (0 <= i < n), 如果以 $(r_h(i), r_h(i + h))$ 为关键字排序,可以得到 $S_{i}$ 的2h序

void da(int str[], int sa[], int rankz[], int height[], int n, int m){ // doubling algorithm
  n++;
  int i, j, p, *x = t1, *y = t2;
  for(i = 0; i < m; i++) c[i] = 0;
  for(i = 0; i < n; i++) c[x[i] = str[i]]++;
  for(i = 1; i < m; i++) c[i] += c[i - 1];
  for(int i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
  for(j = 1; j <= n; j <<= 1){
    p = 0;
    for(i = n - j; i < n; i++){
      y[p++] = i;
    }
    for(i = 0; i < n; i++){
      if(sa[i] >= j) y[p++] = sa[i] - j;
    }
    for(i = 0; i < m; i++) c[i] = 0;
    for(i = 0; i < n; i++) c[x[y[i]]]++;
    for(i = 1; i < m; i++) c[i] += c[i - 1];
    for(i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
    swap(x, y);
    p = 1; x[sa[0]] = 0;
    for(i = 1; i < n; i++){
      x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
    }
    if(p >= n) break;
    m = p;
  }
  int k = 0;
  n--;
  for(i = 0; i <= n; i++) rankz[sa[i]] = i;
  for(i = 0; i < n; i++){
    if(k) k--;
    j = sa[rankz[i] - 1];
    while(str[i + k] == str[j + k]) k++;
    height[rankz[i]] = k;
  }
}

DA算法的复杂度分析

可以看到,DA算法每次倍增后进行排序,直到每一个后缀都有相应的排位后才停止。其中,因为每次做基数排序的时间复杂度是 $O(n)$ 的,而每次排序后会倍增 h 的长度, 所以倍增次数为 $logn$ 级别,总体的时间复杂度是 $O(nlogn)$ ,空间复杂度 $O(n)$

方法2. DC3分治法

DC3算法的实现：

1. 先把文本串的后缀串分成两部分，第一部分是后缀串 $i \ \%\ 3 == 0$ , 第二部分是 $i \ \%\ 3\ != 0$ ，然后先用基数排序对第二部分后缀串排序(按照前三个字符进行排序)。

  int i, j, *rn = r + n;
  int *san = sa + n, ta = 0, tb = (n + 1) / 3, tbc = 0, p;
  r[n] = r[n + 1] = 0; // 添加两个0 便于处理
  for(i = 0; i < n; i++) if(i % 3 != 0) wa[tbc++] = i;
  sort(r + 2, wa, wb, tbc, m);
  sort(r + 1, wb, wa, tbc, m);
  sort(r, wa, wb, tbc, m);

2.把suffix[1]与suffix[2]数组连起来，每三个相邻的字符看做一个数
如果p>=tbc的话，也就是说只排列前三个字符就可以区分出第二部分后缀串的顺序了，否则就要进行递归继续对第二部分的串进行排序。

  for(p = 1, rn[F(wb[0])] = 0, i = 1; i < tbc; i++)
    rn[F(wb[i])] = c0(r, wb[i - 1], wb[i]) ? p - 1 : p++;
  if(p >= tbc) for(i = 0; i < tbc; i++) san[rn[i]] = i; // 如果p>=tbc的话，也就是说只排列前三个字符就可以区分出第二部分后缀串的顺序了。
  else if(p < tbc) dc3(rn, san, tbc, p); // 否则就要进行递归继续对第二部分的串进行排序。

3. 对第一部分后缀来说：

　　 $suffix[3*i] = r[3*i] + suffix[3*i+1];$

　　 $suffix[3*j] = r[3*j] + suffix[3*j+1];$ 我们已知 $i \ \%\ 3 == 1$ 的所有suffix[i]的顺序了，可以利用基数排序很快的求出第一部分后缀的顺序。
4. 第一部分后缀数组和第二部分后缀数组都排好序以后，可以对两部分后缀数组进行一次简单的归并排序，然后就能得到sa数组了。
其中归并排序时需要用到排序函数c12来比较第一部分与第二部分串的大小：

$suffix [3*i] = r[3*i] + suffix[3*i+1]$ ;
$suffix [3*j+1] = r[3*j+1] + suffix[3*j+2]$ ; 已知 $suffix[3*i+1]$ 与 $suffix[3*i+2]$ 所对应的大小关系，可以比较 $r[3*i]$ 与 $r[3*j+1]$ 的大小得出最终结果。
$suffix [3*i] = r[3*i] + suffix[3*i+1]$ ;
$suffix [3*j+2] = r[3*j+2] + suffix[3*(j+1)]$ ; 这个我们可以先比较 $r[3*i]$ 与 $r[3*j+2]$ 的大小，然后再比较 $suffix[3*i+1]$ 与 $suffix[3*(j+1)]$ ，这样就把问题转化为了第一种情况。
```
int c12(int k, int *r, int a, int b){
if(k == 2){
  return r[a] < r[b] || (r[a] == r[b] && c12(1, r, a + 1, b + 1));
}
else return r[a] < r[b] || (r[a] == r[b] && wv[a + 1] < wv[b + 1]);
}
```
复杂度分析[^4]

显然,DC3的空间复杂度是 $O(n)$ 的,我们重点分析一下它的时间复杂度, 对于dc3的分治, 满足递归方程

一般地, 对于递归式子, 我们有以下的结论:
$f(n) = O(n^t) + kf(\frac{n}{m} )$
$f(1) = O(1) 其中， t \ge 0, m > 1, k > 0$
我们有:

$f(n) = O(n^{log_{m}k})$
$f(n) = O(n^tlogn), m^t = k$
$f(n) = O(n^t), m ^ t > k$

DC3 的递归方程里, $m = \frac{3}{2}, t = 1, k = 1, 则m ^ t == \frac{3}{2} > k$
因此, DC3的时间复杂度是 $O(n)$

对于后缀数组学习的感想

关于后缀算法的学习笔记我花了很多天的时间去准备和理解, da算法与dc3算法相比更容易理解, 网上大部分的资料也都是关于da算法的理解。我请教了许多同学, 他们也表示我们只需要熟练掌握da算法,对于dc3算法,仅仅做了解思想即可。dc3虽然在理论上时间复杂度优于da算法, 但是它的常数比较大, 因此其实两者的效率其实相差不大。另外近几年提出了一种新的线性求后缀数组的算法SA-IS,时间上优于DC3, 有时间我会继续去了解新的更优的算法。
在学习后缀数组的时候, 我常常被算法巧妙的设计所震撼, 正是由于构思精妙, 才会让初学者难以理解, 需要对每一步都反复推敲, 即使懂了思想, 在代码细节上也要琢磨透了才能下手, 可以说对代码能力提出了很高的要求。通过后缀数组的学习, 在我在思维和代码能力上都有所提高。
[^3]:参考博客 https://www.luogu.com.cn/blog/xMinh/solution-p3809
[^4]:参考博客 https://www.luogu.com.cn/blog/nederland/guan-yu-di-gui-di-shi-jian-fu-za-du-fen-xi