KMP AC自动机 Z函数
\(s_{0..n-1}\)
前缀函数 \(\pi_i\)
最大的 \(k<i\)
使得 \(s_{0..k-1}=s_{i-k+1..i}\)
abcabcd
\(\pi_0=0\) 规定的
\(\pi_1=0\)
\(\pi_2=0\)
\(\pi_3=1\) abca 的公共前后缀 长度为 1
\(\pi_4=2\) abcab 的公共前后缀 ab 长度为 2
\(\pi_5=3\) abcabc -> abc
\(\pi_6=0\) abcabcd
如何暴力求
vector<int> findpi(string s) {
vector<int> res;
res.push_back(0);
for (int i = 1; i < s.size(); ++i) {
int t = 0;
for (int j = 1; j < i; ++j) {
if (s.substr(0, j) == s.substr(i - j, j))
t = j;
}
res.push_back(t);
}
return res;
}
优化1
\(\pi_{i}\le \pi_{i-1}+1\)
为什么都满足呢？
每次枚举 \(\pi_{i}\) 时，从 \(\pi_{i-1}+1\) 开始从大向小枚举
vector<int> findpi(string s) {
vector<int> res;
res.push_back(0);
for (int i = 1; i < s.size(); ++i) {
int t = 0;
for (int j = res[i - 1] + 1; j > 0; --j) {
if (s.substr(0, j) == s.substr(i - j, j)) {
t = j;
break;
}
}
res.push_back(t);
}
return res;
}
求 \(\pi_i\) 的时候 \(j\) 枚举的范围是 \([\pi_i,\pi_{i-1}+1]\) 所以要 \(\pi_{i-1}+1-\pi_i+1\) 次字符串比较
\[\sum_{i=1}^n(\pi_{i-1}+1-\pi_i+1)=2n+\pi_0-\pi_1+\pi_1-\pi_2+\pi_2-\cdots+\pi_{n-1}-\pi_n\\=2n+\pi_0-\pi_n=2n-\pi_n \]所以需要 \(O(n)\) 次比较字符串（比较一次是 \(O(n)\)）
优化2
vector<int> findpi(string s) {
vector<int> pi;
pi.push_back(0);
for (int i = 1; i < s.size(); ++i) {
int j = pi[i - 1];
while (j > 0 && s[j] != s[i]) j = pi[j - 1];
// 两种情况
// s[j] = s[i]: pi[i] = j + 1
// j = 0: pi[i] = 0
if (s[j] == s[i]) pi.push_back(j + 1);
else pi.push_back(0);
}
return pi;
}
\(O(n)\) 次比较字符
KMP
在大串 \(s\) 中寻找小串 \(p\)
对于 \(ps\) 求前缀函数 \(\pi\)
对于 \(s\) 中的位置 \(t\)，它在 \(ps\) 中的位置是 \(|p|+t\)
只需要看 \(\pi_{|p|+t}\) 是否大于等于 \(|p|\) =>
p=abc
s=cabababcabc
ps = abc|cabababcabc
pi = 000|01212123123
p = abc
ps = abc|abcabcabc
pi = 000|123456789
这么做是不对的。
p = abc
p#s= abc#abcabcabc
pi = 0000123123123
对于 \(p\#s\) 中的 \(s\)，它的 \(\pi\) 是不会超过 \(|p|\)。
vector<int> kmp(string s, string p) {
vector<int> pi = findpi(p);
//
}
一些应用
统计每个前缀 \(s_{0..i}\) 在 \(s\) 的出现次数
考虑前缀 \(s_{0..k}\)
假设对于 \(s_{0..\pi_i-1}\) 而言，它有一个后缀等于 \(s_{0..k}\)
那么 \(s_{0..i}\) 也有一个后缀等于 \(s_{0..k}\)
如果 \(s_{0..i}\) 有一个后缀等于 \(s_{0..k}\)，那么 \(s_{0..\pi_{i}-1}\) 也有
\(s_{0..i}\) 的每一次出现，都代表了一次 \(s_{0..\pi_{i}-1}\) 的出现
有几个本质不同的子串
位置不同，内容相同是本质相同的子串
求 \(s+c\) 会比 \(s\) 多几个本质不同的子串
\(s+c\) 中新产生的本质不同的子串一定是后缀。
如果一个后缀被 \(s\) 包含了，那么比它短的后缀一定也被 \(s\) 包含了
最长的被 \(s\) 包含的后缀
把 \(s+c\) 倒过来，
如果一个前缀被 \(s\) 包含
\(O(n^2)\)
给一个串 和 \(q\) 个询问，每个询问是某个区间的本质不同的子串个数
AC 自动机
int tr[N][26], cnt, leaf[N];
void insert(char *s) {
int n = strlen(s);
int v = 0;
for (int i = 0; i < n; ++i) {
if (!tr[v][s[i] - 'a'])
tr[v][s[i]-'a'] = ++cnt;
v = tr[v][s[i] - 'a'];
}
leaf[v] = 1; // 是字符串的末尾
}
// 怎么求 fail
void build() {
// 假设已经求好了 tr 数组
queue<int> q;
fail[0] = 0;
for (int c = 0; c < 26; ++c) {
if (tr[0][c]) {
fail[tr[0][c]] = 0;
q.push(tr[0][c]);
}
}
while (!q.empty()) {
int h = q.front();
q.pop();
for (int c = 0; c < 26; ++ c) {
if (tr[h][c]) {
fail[tr[h][c]] = tr[fail[h]][c];
q.push(tr[h][c]);
}
else
tr[h][c] = tr[fail[h]][c];
}
}
}
int query(char *s) // s 中出现了几次 p
// p1 = aa p2 = bb, aabbaa 3
{
int u = 0, res= 0, n = strlen(s);
for (int i = 0; i < n; ++i) {
u = tr[u][s[i] - 'a'];
for (int j = u; j && leaf[j]; j = fail[j]) {
res += leaf[j];
leaf[j] = 0;
}
}
return res;
}