KMP & ACAM
stripe_python · · 算法·理论
KMP
问题 1 定义前缀函数
连边
扫描
:::::info[代码]
for (int i = 2, j = 0; i <= n; i++) {
while (j && s[i] != s[j+1]) j = pi[j];
if (s[i] == s[j+1]) j++;
pi[i] = j;
}
:::::
问题 2 给定字符串
取最长匹配长度
接受状态为
问题 3 给定文本串
对
实际上可以避免显式建自动机做到
问题 4(P5829)给定字符串
所有 border 形成树形结构。建 fail 树
ACAM
问题 1 给定字符串
对
定义节点 fail 指针为,当前串的最长真后缀,并且这个后缀对应 Trie 上某个点。转移函数
特别地,根节点失配的转移边是自环。
构造 ACAM 可以在 Trie 上 BFS。对队首节点
- 若
\delta(u,c) 存在,令\text{fail}(\delta(u,c)) \gets \delta(\text{fail}(u),c) 。 - 若
\delta(u,c) 不存在,令\delta(u,c) \gets \delta(\text{fail}(u),c) 。
注 上述过程实际上对 fail 链进行了压缩。最原始的构造方法参见 OI Wiki。
取 Trie 中所有模式串结尾的节点集合
节点数
:::::info[代码]
struct ACAM {
struct node {
int to[26], fail;
} T[N];
int tot = 0;
void insert(const string& s, int id) {
int u = 0;
for (char c : s) {
int& v = T[u].to[c-'a'];
if (!v) v = ++tot;
u = v;
}
}
void build() {
queue<int> Q;
for (int c = 0; c < 26; c++)
if (T[0].to[c]) Q.emplace(T[0].to[c]);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (int c = 0; c < 26; c++) {
int& v = T[u].to[c];
int x = T[T[u].fail].to[c];
if (!v) {v = x; continue;}
T[v].fail = x, Q.emplace(v);
}
}
}
} AC;
:::::
问题 2(P3808)给定模式串
对
跳 fail 链的过程中,遇到被标记点就终止循环,复杂度可以均摊到
问题 3(P5357)给定模式串
对
连边