约定和记号

• S1+S2 表示字符串 S1 和字符串 S2 顺次拼接得到的字符串
• S[L,R] 表示字符串 S 下标从 L 到 R 的字串

字符串哈希

• Hash 是一种常用的字符串算法，可以不需要逐位比较判断两个字符串是否相同
• 最常用的哈希是进制哈希，即选定一个进制 BASE ，将字符串视为一个 BASE 进制下的数，则这个数在模某一个数的意义下的值就是该字符串的哈希值
• 通过比较两个串的哈希值是否相同，即可判断两个串是否相同
• 但是这种做法可能会把两个不同的字符串映射到一个哈希值上，这样就会产生哈希冲突。- - 为了避免或减少哈希冲突，一般有两种方法

哈希链表

多模数哈希

• 将一个串的哈希值对多个质数取模，只有在模每一个质数下的哈希值都相等我们才认为这两个串是相等的
• 这样做实际上是增大了哈希池
• 一般来说两个模数就够了，再多模数会降低速度
• 冲突的概率可以用生日悖论计算

KMP算法

扩展KMP

Manacher算法

AC自动机

后缀数组

后缀自动机

回文自动机