后缀数组是字符串算法的核心。

后缀数组解决什么问题

  • 字符串匹配
  • 最长公共子串
  • 最长重复子串
  • 不同子串个数

核心概念

  • 后缀：字符串从某位置到末尾的子串
  • sa[i]：排名第 i 的后缀起始位置
  • rk[i]：第 i 个后缀的排名
  • height[i]：相邻后缀的最长公共前缀

构造方法

  • 倍增法 O(n log n)
  • DC3 算法 O(n)
  • SA-IS 算法 O(n)

经典应用

  • 字符串匹配（替代 KMP）
  • 最长公共子串
  • 最长回文子串
  • 不同子串个数

省选一对一辅导：151 6522 2880