怎么有铸币还不会写KMP啊？oier失格了属于是
KMP和AC自动机就是给一个DFA加上了一些fail边，使得不存在对应转移时跳到某个之前的状态，而不是直接跳回start节点，以省去不必要的跳转。
先考虑只有一个模式串，这时其实就是KMP。具体的，设文本串为$a_1 a_2 \ldots a_n$，模式串为$b_1 b_2 \ldots b_m$，
我们先考虑naive的做法，把模式串建成trie形的DFA。我们枚举文本串匹配的开头$p$，
若目前有$a_p a_{p+1} \ldots a_{p+s} = b_1 \ldots b_{s+1}$，
但是$a_{p+s+1} \neq b_{s+2}$，则文本串从$p$开始的匹配是失败的，
我们要把$p$前移，并更新DFA状态，开始新的一轮匹配。
Naive approach是$p \leftarrow p + 1$且DFA回到原点。
但我们或许可以通过利用分析这个DFA来排除掉一些不可能的p。
假设我们接下来要从文字串某个位置$p + d > p$开始匹配模式串，
从之前$p$匹配过程留下的DFA状态我们可以知道$a_{p+d} \ldots a_{p+s}$的状态，
只有$a_{p+d} \ldots a_{p+s}$和$b_1 \ldots b_{s+1-d}$匹配，
这样才有接着往下匹配的可能性。
我们发现$a_{p+d} \ldots a_{p+s} = b_{d} \ldots b_{s}$，
也就是说我们需要b的某个前缀等于b的某个后缀。
我们需要从最小的d开始匹配以防漏掉某个结果，也就是说我们要对b的每个前缀$b_1 b_2 \ldots b_s$，
找到最大的$p \in [0,s)$ 使b的长度为p的前缀等于长度为p的后缀。
然后我们在DFA上考虑，对每个节点$u$，我们要找到一个对应的节点$fail[u]$，使得$fail[u]$匹配的串$s_{fail[u]}$是$u$匹配的串$s_u$的最长后缀。
那么这样的fail数组我们要怎么构造呢？考虑从start点开始BFS(因为BFS能保证遍历到某个串时比他短的所有串都被遍历过了)，对某个节点$u$，设$u$读入字符$c$后转移到$to[u,c]$，我们需要算出$fail[to[u,c]]$。而$to[u,c]$的某个后缀一定是$to[suffix(u),c]$的形式。为了保证$to[u,c]$在DFA上，我们首先要有$suffix(u)$在DFA上，并且我们期望suffix(u)尽量长，那么自然的可以想到取$fail[u]$，
若$fail[u]$没有$c$转移，那么比$fail[u]$更短的最长有效后缀在$fail[fail[u]]$。
以此类推，我们需要令$v$从$fail[u]$开始一直跳fail边，直到$v$有$c$转移或$v$到了原点。
然后我们将$fail[to[u,c]]$设为$to[v,c]$，或者原点($v$没有$c$转移时)。
示例代码如下(Luogu P3796)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using std::string;
const int N = 151 * 70, M = 151;
string pattern[M];int end[M];
int ch[N][26];int fail[N];
int cnt[N];
int tot;
int insert(const string &x){
int u = 0;
for(auto c : x){
if(!ch[u][c - 'a']) ch[u][c - 'a'] = ++tot;
u = ch[u][c - 'a'];
}
return u;
}
void build(){
std::queue<int> Q;
for(int i = 0;i < 26;i++){
if(ch[0][i]) Q.push(ch[0][i]);
}
while(!Q.empty()){
int u = Q.front();Q.pop();
for(int c = 0;c < 26;c++){
if(!ch[u][c]) continue;
int p;for(p = fail[u];p && !ch[p][c];p = fail[p]);
if(ch[p][c]) fail[ch[u][c]] = ch[p][c];
Q.push(ch[u][c]);
}
}
}
int main(){
while(1){
memset(ch, 0, sizeof(ch));
memset(fail, 0, sizeof(fail));
memset(cnt, 0, sizeof(cnt));
tot = 0;
int n;std::cin >> n;
if(n == 0) break;
for(int i = 0;i < n;i++){
std::cin >> pattern[i];
end[i] = insert(pattern[i]);
}
build();
string T;std::cin >> T;
int u = 0;for(auto c_ : T){
auto c = c_ - 'a';
for(;u && !ch[u][c];u = fail[u]);
u = ch[u][c];
for(int v = u;v;v = fail[v]) cnt[v]++;
}
int mxcnt = cnt[end[0]];
for(int i = 1;i < n;i++){
mxcnt = std::max(mxcnt, cnt[end[i]]);
}
std::cout << mxcnt << std::endl;
for(int i = 0;i < n;i++){
if(cnt[end[i]] == mxcnt){
std::cout << pattern[i] << std::endl;
}
}
}
return 0;
}
|