后缀数组 [^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] 满足

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

方法1. DA(doubling algorithm)算法

 倍增法的基本思想是,计算 t 的所有位置处长度为2的幂次的前缀的秩, 长度为2h的前缀的秩可以根据长度为 h 的前缀的秩,并利用基数排序算法计算.
 这里需要引入一个定理: 对于 s 的所有后缀(0 <= i < n), 如果以为关键字排序,可以得到的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算法每次倍增后进行排序,直到每一个后缀都有相应的排位后才停止。其中,因为每次做基数排序的时间复杂度是的,而每次排序后会倍增 h 的长度, 所以倍增次数为级别,总体的时间复杂度是,空间复杂度

方法2. DC3分治法

DC3算法的实现:

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

  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[i]的顺序了,可以利用基数排序很快的求出第一部分后缀的顺序。
 4. 第一部分后缀数组和第二部分后缀数组都排好序以后,可以对两部分后缀数组进行一次简单的归并排序,然后就能得到sa数组了。
其中归并排序时需要用到排序函数c12来比较第一部分与第二部分串的大小:

  • ;

  • ; 已知所对应的大小关系,可以比较的大小得出最终结果。

  • ;

  • ; 这个我们可以先比较 的大小,然后再比较 ,这样就把问题转化为了第一种情况。

    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的空间复杂度是的,我们重点分析一下它的时间复杂度, 对于dc3的分治, 满足递归方程

 一般地, 对于递归式子, 我们有以下的结论:


 我们有:

 DC3 的递归方程里,
 因此, DC3的时间复杂度是

对于后缀数组学习的感想

 关于后缀算法的学习笔记我花了很多天的时间去准备和理解, 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