KMP
我们考虑朴素的字符串匹配过程。
void match(const string& s, const string& p) {
// find p in s
for (int i=0; i<s.size(); ++i)
for (int j=0; j<p.size()&&i+j<s.size(); ++j) {
if (s[i+j]!=p[j]) break;
if (j==p.size()-1) {
cout<<"matched at "<<i<<'\n';
}
}
}
对一个字符串 \(s\)，定义 \(\pi[s]\) 为 \(s\) 中最长公共真前后缀的长度。其中真的意思是，其长度必须严格小于 \(|s|\)。
形式化地，定义
\[\pi[s]=\max_{s[1..i]=s[|s|-i+1..|s|],i\lt |s|}\{i\} \]AC 自动机
CF1202E You Are Given Some Strings...
Disclaimer：题解的变量与题目有不同。
定义 \(f(s;p)\) 为 \(p\) 在 \(s\) 中的出现次数。求出
\[\sum_{i=1}^n\sum_{j=1}^n f(s;p_i+p_j) \]其中 \(+\) 代表字符串拼接操作。\(\sum |p_i|,|s|,n\leq 2\times 10^5\)。
我们考虑求出 \(f_i\) 表示有多少个字符串的后缀是 \(s[1..i]\)，\(g_i\) 表示有多少个字符串的前缀是 \(s[i..|s|]\)。于是这部分的贡献为
\[\sum_{i=1}^{|s|-1} f_i\cdot g_{i+1} \]而 \(f,g\) 很易用 AC 自动机求出，具体地，在插入 Trie 树的时候给路径终止的节点的 \(ed\gets ed+1\)，考虑 \(s[i]\) 对应的节点是 \(u\)，则 \(f_i=ed_u\)；对于 \(g\) 可以倒过来做。时间复杂度 \(\Theta(n|\Sigma|)\)。
P3715 [BJOI2017] 魔法咒语
给定 \(n\) 个基本字符串 \(s_i\) 和 \(m\) 个禁止字符串 \(p_i\)；给定正整数 \(l\)。求用基本字符串拼接得到满足以下条件的字符串 \(T\) 的方案数，对 \((10^9+7)\) 取模：
- \(|T|=l\)；
- \(T\) 中不存在任意一个 \(m_i\) 作为子串。
对于 \(1\sim 6\) 号测试点，\(n,m\leq 50\)，\(l\leq 10^2\)；
对于 \(7\sim 10\) 号测试点，\(|s_i|\leq 2\)，\(l\leq 10^8\)。
保证 \(\sum |s_i|,\sum |m_i|\leq 10^2\)。
对于前一部分，套路地考虑 dp。设 \(f[l,i]\) 为长度为 \(l\) 时，在节点 \(i\) 处的方案数量。于是设 \(u\overset{s_i}{\to}v_{u,s_i}\)，我们有
\[f[i+|s_i|,v_{u,s_i}]\gets f[i,u]+f[i+|s_i|,v_{u,s_i}] \]其中要求 \(u\to v_{u,s_i}\) 不能经过 \(p_i\) 的终止节点。于是这一部分时间复杂度为 \(\Theta(l\sum|s_i|\sum|p_i|)\)，极限数据下不大于 \(10^6\)，可以通过。
对于后一部分，基于 \(|s_i|\leq 2\)，考虑矩阵快速幂优化。
后缀数组
后缀自动机
P2463 [SDOI2008] Sandy 的卡片
给定 \(n\) 个数列 \(A_i,\cdots,A_n\)。求这 \(n\) 个数列的最长公共子串长度。
“相同”的定义：\(a_i\) 与 \(b_i\) 相同当且仅当 \(a_1-b_1=a_2-b_2=\cdots=a_n-b_n\)。
值域为 \([0,2\times 10^3]\)，\(n\leq 10^3\)。
标签：10,常用,..,后缀,sum,leq,算法,字符串 From： https://www.cnblogs.com/Starrykiller/p/18024058/string-theory