Trie
很简单的东西,这里就不阐述了。
const int N = 400005 + 111;
struct Trie{
int nxt[N][27], cnt;
int vis[N];
void init(){
memset(nxt, 0, sizeof nxt);
memset(vis, 0, sizeof vis);
cnt = 0;
}
void insert(char *s){
int len = strlen(s), u = 0;
for(int i = 0; i < len; i ++){
int c = s[i] - 'a' + 1;
if(!nxt[u][c]) nxt[u][c] = ++cnt;
u = nxt[u][c];
}
vis[u] = 1;
}
bool find(char *s){
int len = strlen(s), u = 0;
for(int i = 0; i < len; i ++){
int c = s[i] - 'a' + 1;
if(!nxt[u][c]) return false;
u = nxt[u][c];
}
return vis[u];
}
}trie;
KMP
用于单模板的字符串匹配问题,预处理是均摊 \(O(m)\) 的,匹配是均摊 \(O(n)\) 的。
朴素的算法是枚举起始位置,暴力匹配,时间复杂度是 \(O(m(n-1))\) 的,但是在随机数据下表现良好。
考虑优化。
定义失配函数 \(fail_i\) 为最长的前缀的长度,满足是其模板串的后缀。
\(t = "aabccseaabcc"\)
其各个前缀的 \(fail\) 函数为:
\(P_1 = 0,P_2 = 1,P_3 = 0,P_4 = 0, P_5 = 0, P_6 = 0, P_7 = 0\)
\(P_8 = 1, P_9 = 2, P_{10} = 3, P_{11} = 4, P_{12} = 5\)
剩下的就是改变暴力的方式,如果下一个字符不匹配暴力跳 \(fail\) 即可。
求 \(fail\) 函数本质上是自己匹配自己。
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); i ++)
const int N = 1e6 + 11;
char A[N], B[N]; int P[N];
void P_function(char *s, int len){
P[0] = P[1] = 0;
int j = 0;
_for(i, 2, len){
while(j and s[j+1] != s[i]) j = P[j];
if(s[j+1] == s[i]) j++;
P[i] = j;
}
}
void MP(char *text, char *moban, int len1, int len2){
int j = 0;
_for(i, 1, len1){
while(j and text[i] != moban[j+1]) j = P[j];
if(text[i] == moban[j+1]) j++;
if(j == len2){
printf("%d\n", i - len2 + 1);
j = P[j];// 继续匹配
}
}
}
int main(){
scanf("%s", A+1);
scanf("%s", B+1);
int n = strlen(A+1), m = strlen(B+1);
P_function(B, m);
MP(A, B, n, m);
_for(i, 1, m) printf("%d ", P[i]);
puts("");
return 0;
}
\(Aho Corasick Automaton\) (\(AC\) 自动机)
自动 \(AC\)。
把 \(KMP\) 的 \(fail\) 函数扔到 \(Tire\) 上即可。
具体的,对于一个节点 \(u\) , \(fail_u\) 为 整个 \(Trie\) 树上的最深的节点,满足其是 \(u\) 代表的字符串的前缀与后缀。
为了简化 找 \(fail\) 的过程,我们可以对 \(nxt\) 数组,也就是 \(Trie\) 树进行改造。
具体的,对于一个原来不存在的 \(nxt[u][c]\) ,我们将其赋值为 不断跳 \(fail\) 指针,找到的第一个真实存在的 \(nxt[fail[\dots fail[u]]][c]\)。
因此我们在匹配时不用跳 \(fail\) 指针,大大缩短了时间,对于一个原来不存在的 \(nxt[u][c]\) 赋值,实际上就是 \(nxt[u][c] = nxt[fail[u]][c]\)。
其正确性显然
如果 \(nxt[fail[u]][c]\) 不是真实存在的,其值一定是 \(nxt[fail[fail[u]]][c]\),以此类推,一定会指向真实的 \(nxt[fail[\dots fail[u]]][c]\) 或 \(0\)。
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <cstdio>
#include <iostream>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); i ++)
#define _rep(i, a, b) for(int i = (a); i >= (b); i ++)
const int N = 150 * 77;
struct Aho_Corsick_Automaton{
int nxt[N][28], vis[N], fail[N];
int cnt, tot[N];
void init(){
memset(nxt, 0, sizeof nxt);
memset(vis, 0, sizeof vis);
memset(fail, 0, sizeof fail);
memset(tot, 0, sizeof tot);
cnt = 1;
}
void insert(char *s, int id){
int u = 1, len = strlen(s);
_for(i, 0, len - 1){
int c = s[i] - 'a' + 1;
if(!nxt[u][c]) nxt[u][c] = ++cnt;
u = nxt[u][c];
}
vis[u] = id;
}
void failure_function(){
_for(i, 0, 26) nxt[0][i] = 1;
queue<int> q; q.push(1);
fail[1] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
_for(c, 1, 26){
int v = nxt[u][c];
if(!v){
nxt[u][c] = nxt[fail[u]][c];
continue;
}
fail[v] = nxt[fail[u]][c];
q.push(v);
}
}
}
int appear;
void find_text(char *s){
appear = 0;
int len = strlen(s), u = 1;
_for(i, 0, len-1){
int c = s[i] - 'a' + 1;
int v = nxt[u][c];
while(v > 1){
if(vis[v])
appear = max(appear, ++tot[vis[v]]);
v = fail[v];
}
u = nxt[u][c];
}
}
}Automaton;
char moban[155][77], text[1000000 + 11];
int main(){
int n = 0;
while(scanf("%d", &n) == 1 and n != 0){
Automaton.init();
_for(i, 1, n){
scanf("%s", moban[i]);
Automaton.insert(moban[i], i);
}
Automaton.failure_function();
scanf("%s", text);
Automaton.find_text(text);
printf("%d\n", Automaton.appear);
_for(i, 1, n){
if(Automaton.appear == Automaton.tot[i])
printf("%s\n", moban[i]);
}
}
return 0;
}
练习
Remember the Word UVA 1401
题意
给出一个由 \(S\) 个不同单词组成的字典和一个长字符串,把该长字符串分解为若干个单词的连接,有多少种方法?
\(1 \le |Len| \le 3\times10^{5}, 1 \le S \le 4000, 1 \le Len_i \le 100\)。
分析
考虑 \(dp\) 求解。
定义 \(f_i = sum\{ f_{i+len_x} | x \text{是} S[i \dots len_S] \text{的前缀} \}\),边界条件为 \(f_{len_S+1} = 1\)。
找 \(x\) 实际上是在由模板串组成的 \(Trie\) 上匹配 \(S[i \dots len_S]\) 的过程。
时间复杂度为 \(O(100(Len_s + S))\)。
代码
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
const int mod = 20071027;
const int N = 400005 + 111;
struct Trie{
int nxt[N][27], cnt;
int c[N];
void init(){
memset(nxt, 0, sizeof nxt);
memset(c, 0, sizeof c);
cnt = 0;
}
void insert(char *s){
int len = strlen(s), u = 0;
for(int i = 0; i < len; i ++){
int to = s[i] - 'a' + 1;
if(!nxt[u][to]){
nxt[u][to] = ++cnt;
}
u = nxt[u][to];
}
c[u] = len;
}
void query(char *s, int from, int to, vector<int> &r){
int u = 0;
for(int i = from; i <= to; i ++){
if(s[i] == '\0') break;
int v = s[i] - 'a' + 1;
if(!nxt[u][v]) break;
u = nxt[u][v];
if(c[u]) r.push_back(c[u]);
}
return;
}
}trie;
int n, F[300000 + 11];
char s1[300000 + 11], s2[300000 + 11];
int main(){
int T = 0;
while(scanf("%s", s1) == 1){
scanf("%d", &n);
memset(F, 0, sizeof F);
trie.init();
for(int i = 0; i < n; i ++){
scanf("%s", s2);
trie.insert(s2);
}
int n = strlen(s1) - 1;
F[n + 1] = 1;
for(int i = n; i >= 0; i --){
vector<int>pufer;
trie.query(s1, i, n, pufer);
for(auto j:pufer){
(F[i] += F[i + j]) %= mod;
}
}
printf("Case %d: %d\n", ++T, F[0]);
}
return 0;
}
"strcmp()" Anyone? UVA 11732
题意
\(strcmp()\) 的实现如下:
int strcmp(char *s, char *t)
{
int i;
for (i=0; s[i]==t[i]; i++)
if (s[i]=='\0')
return 0;
return s[i] - t[i];
}
求 \(\sum_{i=1}^{n}\sum_{j=i+1}^{n} chk(strcmp(S_i,S_j))\),其中 \(chk(strcmp(S_i,S_j))\) 为 \(strcmp(S_i,S_j)\) 的比较次数。
分析
扔到 \(Trie\) 树上,手玩一下即可发现规律(计算每个节点的贡献)。
代码
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long lgt;
const lgt N = 4e6 + 11;
struct Trie{
lgt ct[N], cnt;
lgt h[N], to[N], w[N], nt[N];
lgt ans, tot;
void init(){
memset(h, 0, sizeof h);
memset(to, 0, sizeof to);
memset(w, 0, sizeof w);
memset(nt, 0, sizeof nt);
memset(ct, 0, sizeof ct);
ans = tot = cnt = 0;
}
void add(lgt x, lgt y, lgt z){
nt[++tot] = h[x];
h[x] = tot;
w[tot] = z;
to[tot] = y;
}
void insert(char *s){
lgt u = 0, len = strlen(s);
ct[u]++;
for(lgt i = 0; i <= len; i ++){
lgt c = (lgt)s[i], v = -1, ww;
for(lgt j = h[u]; j; j = nt[j]){
lgt To = to[j], W = w[j];
if(W == c){
v = To;
break;
}
}
if(v == -1){
v = ++cnt;
add(u, v, c);
}
u = v;
ct[u]++;
}
return;
}
void DP(lgt u, lgt dep){
if(h[u] == 0) {
ans += ct[u] * (ct[u]-1) * dep;
return;
}
lgt sum = 0;
for(lgt i = h[u]; i; i = nt[i]){
lgt y = to[i];
sum += ct[y] * (ct[u] - ct[y]);
}
ans += sum / 2 * (dep * 2 + 1);
for(lgt i = h[u]; i; i = nt[i]){
lgt y = to[i];
DP(y, dep+1);
}
return;
}
lgt out(){ans = 0; DP(0, 0); return ans;}
};
lgt n;
char word[N];
Trie trie;
int main() {
lgt kase = 0;
while(scanf("%lld", &n) == 1 && n) {
trie.init();
for(lgt i = 0; i < n; i++) {
scanf("%s", word);
trie.insert(word);
}
printf("Case %lld: %lld\n", ++kase, trie.out());
}
return 0;
}
Period SP263&UVA1328
题意
对于给定字符串 \(S\) 的每个前缀,我们想知道它是否为周期串(周期串定义为由若干最小循环节拼接而成的字符串),若是,输出前缀长度和循环节数量。
分析
构造 \(fail\) 函数,考虑 \(fail_i\) 的性质(前缀等于后缀)。
代码
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); i ++)
const int N = 1e6 + 11;
int P[N]; char r[N];
void failure_function(char *moban, int len){
int j = 0; P[0] = P[1] = 0;
_for(i, 2, len){
while(j and moban[j+1] != moban[i]) j = P[j];
if(moban[j+1] == moban[i]) j++;
P[i] = j;
}
}
int main(){
int T = 0,n, kase = 0;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
scanf("%s", r+1);
failure_function(r, n);
printf("Test case #%d\n", ++kase);
_for(i, 2, n){
if(P[i] and i % (i - P[i]) == 0) printf("%d %d\n", i, i / (i-P[i]));
}
puts("");
}
return 0;
}
Dominating Patterns UVA1449
题目
分析
由于可能出现相同的字符串,开 \(vector\) 记录出现的字符串,统计答案时暴力跳 \(fail\) 统计即可。
代码
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <queue>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
const int N = 155;
const int M = 77;
const int P = 1e6 + 11;
const int Q = 155 * 77;
struct Aho_Corasick_Automaton{
int nxt[Q][28], fail[Q], cnt, tot[N], vis[Q], max_appear;
map< int, vector<int> > ID;
void init(){
memset(nxt, 0, sizeof nxt);
memset(fail, 0, sizeof fail);
memset(vis, 0, sizeof vis);
memset(tot, 0, sizeof tot);
ID.clear();
cnt = 1;
}
void insert(char *s, int id){
int u = 1, len = strlen(s);
_for(i, 0, len - 1){
int c = s[i] - 'a' + 1;
if(!nxt[u][c]) nxt[u][c] = ++cnt;
u = nxt[u][c];
}
ID[u].push_back(id);
}
void failure_function(){
_for(i, 1, 27) nxt[0][i] = 1;
queue<int> q; q.push(1);
int u = 1; fail[1] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
_for(i, 1, 26){
static int c, v;
c = i; v = nxt[u][c];
if(!nxt[u][c]){
nxt[u][c] = nxt[fail[u]][c];
continue;
}
fail[v] = nxt[fail[u]][c];
q.push(v);
}
}
}
void find_text(char *s){
int u = 1, len = strlen(s);
max_appear = 0;
_for(i, 0, len-1){
int c = s[i] - 'a' + 1;
int v = nxt[u][c];
while(v > 1){
if(ID.count(v)){
for(auto j:ID[v]){
tot[j]++;
max_appear = max(max_appear, tot[j]);
}
}
v = fail[v];
}
u = nxt[u][c];
}
}
}AC_Automaton;
char moban[N][M], text[P];
int main(){
int n;
while(scanf("%d", &n) == 1 and n != 0){
AC_Automaton.init();
_for(i, 1, n){
scanf("%s", moban[i]);
AC_Automaton.insert(moban[i], i);
}
scanf("%s", text);
AC_Automaton.failure_function();
AC_Automaton.find_text(text);
printf("%d\n", AC_Automaton.max_appear);
_for(i, 1, n){
if(AC_Automaton.max_appear == AC_Automaton.tot[i]){
printf("%s\n", moban[i]);
}
}
}
return 0;
}
Substring UVA11468
题目
分析
直接建立 \(ACAM\) ,\(DP\) 计算答案即可。
daima
#include <queue>
#include <map>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstdio>
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
const int N = 4e4 + 5;
int Is(char c){
if(isdigit(c)) return c - '0';
else if(islower(c)) return c - 'a' + 11;
else return c - 'A' + 37;
}
struct Aho_Corsick_Automaton{
int nxt[N][77], cnt;
int fail[N];
bool vis[N];
double f[N][200];
double p[77];
bool h[N][200];
void init(){
memset(nxt, 0, sizeof nxt);
memset(vis, 0, sizeof vis);
memset(fail, 0, sizeof fail);
memset(f, 0, sizeof f);
memset(p, 0, sizeof p);
memset(h, 0, sizeof h);
cnt = 1;
}
void insert(char *s){
int u = 1, len = strlen(s);
_for(i, 0, len - 1){
int c = Is(s[i]);
if(!nxt[u][c])nxt[u][c] = ++cnt;
u = nxt[u][c];
}
vis[u] = 1;
}
void failure_function(){
_for(i, 0, 70) nxt[0][i] = 1;
queue<int> q; q.push(1);
fail[1] = 0;
while(!q.empty()){
int u = q.front();
q.pop();
_for(i, 0, 70){
int c = i, v = nxt[u][c];
if(!v){
nxt[u][c] = nxt[fail[u]][c];
continue;
}
fail[v] = nxt[fail[u]][c];
q.push(v);vis[u] |= vis[fail[u]];
}
}
}
double dfs(int now, int len){
if(len == 0) return 1.0;
if(h[now][len] == true)
return f[now][len];
double &ans = f[now][len];
h[now][len] = true;
ans = 0.000;
_for(i, 0, 70){
if(vis[nxt[now][i]]) continue;
ans += p[i] * dfs(nxt[now][i], len-1);
}
return ans;
}
}AC_Automaton;
char moban[1111];
int main(){
int T, kase = 0;
cin >> T;
while(T--){
AC_Automaton.init();
int n, k, l;
cin >> n;
_for(i, 1, n){
scanf("%s", moban);
AC_Automaton.insert(moban);
}
AC_Automaton.failure_function();
cin >> k;
_for(i, 1, k){
char c;
double p;
cin >> c >> p;
AC_Automaton.p[Is(c)] = p;
}
cin >> l;
printf("Case #%d: %.6lf\n", ++kase, AC_Automaton.dfs(1, l));
}
return 0;
}
标签:nxt,Automaton,int,基础,len,fail,算法,字符串,include
From: https://www.cnblogs.com/dadidididi/p/17074031.html