跳转至

String

  • 分类于 String
  • 需要 4 分钟阅读时间

后缀数组

后缀数组是处理字符串的利器。

定义

对于长度为 \(n\) 的字符串 \(s = s_1 s_2 \cdots s_n\)，定义 \(s[i,j] = s_i s_{i+1} \cdots s_j\)，即 \(s\) 的第 \(i\) 个到第 \(j\) 个字符形成的子串。

定义 sa 为 \(s\) 的后缀数组，sa[i] 表示第 \(i\) 小的后缀的编号。

定义 rk[sa[i]]=i，即 rk[i] 表示后缀 \(i\) 的 rank。