构造

  • O(n\log n) : 倍增
  • O(n) : Dc3 无卵用感觉

性质

关于SA, 令h_i=\text{height}_{rank_i}, 有

  • h_i\geq h_{i-1}-1

自己画画图就明白了吧…

  • \text{本质不同的串个数}= \binom{n+1}{2}-\sum h_i

    正是可以利用性质1, 我们就可以在线性的复杂度内求出\text{height}数组!

Trick

简单介绍一些关于SA的技巧

==这些技巧可以始终和调和级数结合在一起==

  1. 杂记
  • 给定一个字符串,询问某两个后缀的最长公共前缀

    \text{sol}:发现两个串的lcp就是所在height区间的最小值

    RMQ搞搞就好了

  • 给定一个字符串,求最长重复子串,这两个子串可以重叠

    \text{sol}:考虑暴力做法, 相当于枚举\text{suffix}(i)\text{suffix}(j) 它们的lcp就可以对答案做一次贡献

    但是这样是n^2的, 进一步的, 如果|\text{rank}_i-\text{rank}_j|>1 发现一定不会比\text{rank}是相邻的优!(区间\min)

    那么就相当于是O(n)求height最大值即可…

  1. \text{height}分组

主要的依据:

假设按照x大小分组, 那么每一组里面的元素都是不小于x的height

如果超出该区间就会使lcp小于x, 于是就gg了

看不懂就看题目吧

  • 给定一个字符串,求最长重复子串,这两个子串不能重叠

    \text{sol}: 显然, 答案是具有二分性质的!

    题目转化为验证k是否成立: 对\text{height}进行关于k的分组, 那么我们只要看一下这个区间内的长度最长的后缀减去长度最短的后缀是否不小于k即可!

  • 给定一个字符串,求至少出现 k 次的最长重复子串,这 k 个子串可以重叠

    \text{sol}: 类似上一题

    ==发现题目中出现>k的关键词就可以考虑\text{height}分组==

  1. 拼串

对于两个字符串或者多个字符串的题目, 可以考虑中间利用$连接, 然后进行魔改

  • 给定一个字符串,求最长回文子串

    \text{sol}: 正串 + 反串即可

  • 给定一个字符串 L,已知这个字符串是由某个字符串 S 重复 R 次而得到的,
    求 R 的最大值

    \text{sol}: 我们既然已经知道它是一个循环串, 意味着我们需要找到可能的\text{border}

    那么就可以枚举\text{suffix}(i)\text{suffix}(1)lcp即可, 这里不需要RMQ, O(n)预处理就好了.

Lemma

判断一个字符串s是否是严格周期串, 当且仅当p_{min}\mid \ |s|

p_{min}s的最小周期.

Prove

:joy: 幼小

  1. 如果a, b均为s的周期, 那么\gcd(a,b) 也为s的周期

考虑上面的图片, 部分1根据绿色的周期可以等于部分2, 部分2根据红色的周期可以等于部分3…

那么可得(a-b)也是一个周期, 那么\gcd(a,b)s周期就显然了(更相减损)

  1. 回归题面

p_{min}\mid \ |s| 那么s必定是一个严格周期串.

反之, 如果存在p_{min}\nmid |s|\exists p, p > p_{min} \ s.t. p \mid |s|

那么根据1的推论, 发现\gcd(p_{min},p)同样是周期, 而且\gcd(p_{min},p)\mid |s|

那么就矛盾了…

\nexists p, p>p_{min} \ s.t. p \mid |s|那么由于不存在, 那么就不会是一个严格周期串.

证毕…

Leave a Reply