字符串算法

字符串算法

字符串处理是竞赛中的常见题型。共 4 个模板。

← 返回模板库

10.1KMP 算法

利用 next 数组跳过不必要的比较，高效字符串匹配

O(n + m)

10.2Trie 字典树

多模式串存储与查询，公共前缀共享

O(L) 插入/查询

10.3Manacher 算法

O(n) 求所有回文子串的最长半径

O(n)

10.4AC 自动机

Trie + 失配指针，多模式串同时匹配

O(n + m + 匹配数)