ac自动机模板三巨头

学会了也不能AC…

AC自动机

出现的模式串个数

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
char s[N];
int trie[N][26],tot=0,ed[N],fail[N],n;
void ins(char *s){
int len=strlen(s), p=0;
rep(i,0,len-1){
int c = s[i]-'a';
if(!trie[p][c]) trie[p][c] = ++tot;
p = trie[p][c];
}
ed[p] ++;
}
void getfail(){
queue<int> q;
rep(i,0,25)
if(trie[0][i])
q.push(trie[0][i]);
while(!q.empty()){
int x = q.front(); q.pop();
rep(i,0,25){
if(trie[x][i]){
fail[trie[x][i]] = trie[fail[x]][i];
q.push(trie[x][i]);
}
else trie[x][i] = trie[fail[x]][i];
}
}
}
int query(char *s){
int ans=0, now=0, len=strlen(s);
rep(i,0,len-1){
now = trie[now][s[i]-'a'];
for(int j=now; j && ~ed[j]; j=fail[j]){
ans += ed[j], ed[j] = -1;
}
}
return ans;
}
int main(){
scanf("%d",&n);
rep(i,1,n){
scanf("%s",s);
ins(s);
}
getfail();
scanf("%s",s);
printf("%d\n",query(s));
return 0;
}

出现最多的模式串

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
int tot=0,n,fail[N],trie[N][30],ed[N],num[N];
char str[200][100], ptr[M];
void init(){
tot=0;
clr(ed,0);clr(fail,0);
clr(trie,0);clr(num,0);
}
void ins(int t, char *s){
int len=strlen(s), p=0;
rep(i,0,len-1){
int c=s[i]-'a';
if(!trie[p][c]) trie[p][c] = ++tot;
p = trie[p][c];
}
ed[p] = t;
}
void getfail(){
queue<int> q;
rep(i,0,25)
if(trie[0][i])
q.push(trie[0][i]);
while(!q.empty()){
int x = q.front(); q.pop();
rep(i,0,25){
if(trie[x][i]){
fail[trie[x][i]] = trie[fail[x]][i];
q.push(trie[x][i]);
}
else trie[x][i] = trie[fail[x]][i];
}
}
}
int query(char *s){
int now=0, len=strlen(s), ans = -1;
rep(i,0,len-1){
now = trie[now][s[i]-'a'];
for(int j=now; j; j=fail[j]){
if(ed[j]) {
num[ed[j]]++;
ans = max(ans, num[ed[j]]);
}
}
}
return ans;
}
int main(){
while(~scanf("%d",&n)&&n){
init();
rep(i,1,n){
scanf("%s",str[i]);
ins(i,str[i]);
}
getfail();
scanf("%s",ptr);
int mx = query(ptr);
printf("%d\n",mx);
rep(i,1,n)
if(num[i] == mx)
printf("%s\n",str[i]);
}
return 0;
}

每个模式串的出现次数
fail树上差分

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
68
int tot=0,fail[N],trie[N][30],ed[N],v[N];
int cnt=0,n,head[N],num[N];
string str[N], ptr;
struct edge{
int to,next;
}e[N];
void add(int x,int y){
e[cnt] = {y,head[x]};
head[x] = cnt++;
}
void dfs(int x){
for(int i=head[x];~i;i=e[i].next){
int y=e[i].to;
dfs(y);
num[x] += num[y];
}
}
void ins(int t,string s){
int len=s.size(), p=0;
rep(i,0,len-1){
int c = s[i]-'a';
if(!trie[p][c]) trie[p][c] = ++tot;
p = trie[p][c];
}
ed[p]=t;
v[t] = p;
}
void getfail(){
queue<int> q;
rep(i,0,25)
if(trie[0][i])
q.push(trie[0][i]);
while(!q.empty()){
int x=q.front(); q.pop();
rep(i,0,25){
if(trie[x][i]){
fail[trie[x][i]] = trie[fail[x]][i];
q.push(trie[x][i]);
}
else trie[x][i] = trie[fail[x]][i];
}
}
}
void query(string s){
int len=s.size(), x=0;
rep(i,0,len-1){
x = trie[x][s[i]-'a'];
num[x]++;
}
rep(i,1,tot) add(fail[i],i);
dfs(0);
rep(i,1,n)
cout<<num[v[i]]<<endl;
}
int main(){
ios::sync_with_stdio(false);
clr(head,-1);
cin>>n;
rep(i,1,n){
cin>>str[i];
ins(i,str[i]);
}
getfail();
cin>>ptr;
query(ptr);
return 0;
}

Donate comment here