诈尸式更新!

如你所见,这是个导航文章 =3=

导航之前,还得给字符串做一些约定:

  • 下标从 0 开始
  • S(i) 表示 S 上下标为 i 的位置的字符
  • \text{substr}(S, i, j) 表示字符串 S 从第 i 个位置到第 j - 1 个位置的子串
  • \text{suf}(S, i) 表示字符串 S 从第 i 位置到末尾的子串,即 \text{substr}(S, i, |S|)。也称为第 i 个后缀、后缀 i
  • \text{pre}(S, i) 表示字符串 S 从开头到第 i - 1 个位置子串,即 \text{substr}(0, i - 1)。也称为第 i 个前缀、前缀 i
  • 若无特殊说明,上述所有约定的第一个参数可以省略,并认定为上一个提到的字符串
  • 子序列的下标不连续,子串连续
  • \text{LCP}(S, T) 表示字符串 S, T 的最长公共前缀这个字符串

然后是导航:

OI-字符串 OI-字符串-SAM后缀自动机 OI-字符串-SA后缀数组

None
上一篇 «
11-25 赛后题解与复盘总结
» 下一篇