最小表示法

时空复杂度: \(O(n)\)

MyCode

Manacher

使用时type要传入的参数奇串为\(0\)，偶串为\(1\).

偶回文串\(S[l\cdots r]\)的回文中心定义为\(\lfloor \frac{l+r}{2} \rfloor\)

时空复杂度: \(O(n)\)

MyCode

Kmp

时空复杂度: \(O(n)\)

MyCode

Shift-And Algorithm

时空复杂度：\(O(nm/\alpha)\)

MyCode

Suffix Array

倍增法构造

时间复杂度：\(O(n\log{n})\)

空间复杂度：\(O(n)\)

MyCode

Suffix Automaton

时空复杂度：\(O(n\Sigma)\).

Mycode