AC自动机的学习

icpc字符串AC自动机

洛谷的板子

题目1

1

标程

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
#include<queue>
#define maxn 1000001
using namespace std;
bool b[maxn];
string word,s;
int ans=0;
typedef struct A{
    A *fail;
    A *next[26];
    int word;
    int num;
    void a(){
        for(int i=0;i<26;i++){
            next[i]=NULL;
        }
        fail=NULL; 
        word=0;
        num=0;
    }
}node;
node *root;
void insert_word(int j){
    int len=word.length();
    node *p=root;
    for(int i=0;i<len;i++){
        int k=word[i]-'a';
        if(p->next[k]==NULL){
            node *temp;
            temp=new node;
            temp->a();
            p->next[k]=temp;
        }
        p=p->next[k];    
    }
    p->word=j;
    p->num++;
}
void fail(){
    queue<node *>q;
    q.push(root);
    while(!q.empty()){
        node *p=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            if(p->next[i]!=NULL){
                node *t=p->next[i];
                if(p==root){
                    t->fail=root;
                }
                else{
                    node *fafail=p->fail;
                    while(fafail!=NULL){
                        if(fafail->next[i]!=NULL){
                            t->fail=fafail->next[i];
                            break;
                        }
                        fafail=fafail->fail;
                    }
                    if(fafail==NULL)t->fail=root;
                }
                q.push(t);
            }
        }
    }
}
void query(){
    int len=s.length();
    node *p=root;
    for(int i=0;i<len;i++){
        int k=s[i]-'a';
        while(p!=root&&p->next[k]==NULL)
            p=p->fail;
        p=p->next[k];
        if(p==NULL)
            p=root;
        node *temp=p;
        //while(temp!=root){
            if(temp->word&&!b[temp->word]){
                b[temp->word]=1;
                ans+=temp->num;
            }
        //    temp=temp->fail;
        //}
    }
}
/*
int c[10001];
int all=0;
void print(){
    for(int i=1;i<=all;i++){
        printf("%c",b[i]+'a');
    }
    cout<<endl;
}
void dfs(node *t){
    if(t->word)print();
    for(int i=0;i<26;i++){
        if(t->next[i]!=NULL){
            c[++all]=i;
            dfs(t->next[i]);
            all--;
        }
    }
    
}*/
int main(){
    //freopen("P3808.in","r",stdin);
    //freopen("P3808.out","w",stdout);
    root=new node;
    root->a();
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>word;
        insert_word(i);
    }
    //dfs(root);
    
    fail();
    while(cin>>s){
        ans=0;
        query();
        cout<<ans<<endl;
    }
}

题目2

2

标程

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
typedef struct A{
    int word;
    A* fail;
    A* next[26];
    void aaa(){
        word=0;
        fail=NULL;
        for(int i=0;i<26;i++)
            next[i]=NULL;
    }
}node;
node *root;
queue<node*>q;
map<string,int>tmap;
string word[200];
char t[1000010];
int num[200];
void insert(int x){
    node *p=root;
    int len=word[x].length();
    for(int i=0;i<len;i++){
        int k=word[x][i]-'a';
        if(p->next[k]==NULL){
            node *new_node=new node;
            new_node->aaa();
            p->next[k]=new_node;
        }
        p=p->next[k];
    }
    p->word=x;
}
void build_fail(){
    q.push(root);
    while(!q.empty()){
        node *p=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            if(p->next[i]!=NULL){
                node *k=p->next[i];
                q.push(k);
                if(p==root){
                    k->fail=root;
                }
                else{
                    node *fafail=p->fail;
                    while(fafail!=NULL){
                        if(fafail->next[i]!=NULL){
                            k->fail=fafail->next[i];
                            break;
                        }
                        fafail=fafail->fail;
                    }
                    if(fafail==NULL)k->fail=root;
                }
            }
        }
    }
}
void query(){
    int len=strlen(t);
    node *p=root;
    for(int i=0;i<len;i++){
        int k=t[i]-'a';
        while(p->next[k]==NULL&&p!=root)p=p->fail;
        p=p->next[k];
        if(p==NULL)p=root;
        else{
            node *temp=p;
            while(temp!=root){
                if(temp->word){
                    num[temp->word]++;
                }
                temp=temp->fail;
            }
        }
    }
}
int cmp1(int a,int b){
    return a>b;
}
int cmp(string a,string b){
    if(num[tmap[a]]==num[tmap[b]])return tmap[a]<tmap[b];
    return num[tmap[a]]>num[tmap[b]];
}
int main(){
    //freopen("in.txt","r",stdin);
    int n;
    while(scanf("%d",&n)&&n){
        memset(num,0,sizeof(num));
        tmap.clear();
        root=new node;
        root->aaa();
        for(int i=1;i<=n;i++){
            cin>>word[i];
            tmap[word[i]]=i;
            insert(i);
        }
        build_fail();
        scanf("%s",t);
        query();
        sort(word+1,word+1+n,cmp);
        sort(num+1,num+1+n,cmp1);
        int maxnum=num[1];
        cout<<maxnum<<endl;
        for(int i=1;i<=n;i++){
            if(num[i]==maxnum){
                cout<<word[i]<<endl;
            }
        }
    }
    return 0;
}

题目3

3

标程

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int maxn = 2e6 + 5;
struct node{
    int word;int deg,val;
    node *fail , *next[26];
    node() {
        word = deg = val = 0;fail = NULL;
        for (int i = 0;i < 26;i++)
            next[i] = NULL;
    }
}*ext=(node*)malloc(sizeof(node)*maxn),*root;

queue<node*> Q;
char t[maxn], word[maxn];int num[maxn],ans[maxn];

inline node* Ot(){return *ext=node(),ext++;}

void insert(int x) {
    node* p = root;
    int len = strlen(word);
    for (int i = 0;i < len;i++) {
        int k = word[i] - 'a';
        if (p->next[k] == NULL) {
            p->next[k] = Ot();
        }
        p = p->next[k];
    }
    if (!p->word) {
        p->word = x;
    }
    num[x] = p->word;
}
void build_fail() {
    for(int i=0;i<26;i++) if(root->next[i]) root->next[i]->fail=root,Q.push(root->next[i]); else root->next[i]=root;
    while (!Q.empty()) {
        node* p = Q.front();Q.pop();
        // printf("%ld\n",p-root);
        for (int i = 0;i < 26;i++) {
            if (p->next[i]) {
                p->next[i]->fail = p->fail->next[i],p->fail->next[i]->deg++;
                if(p->next[i]!=root) Q.push(p->next[i]);
            }
            else p->next[i] = p->fail->next[i];
        }
    }
}

void query() {
    int len = strlen(t);
    // printf("len:%d\n",len);
    node* p = root;
    for (int i = 0;i < len;i++) {
        // printf("i:%d p:%ld np:%ld\n",i,p-root,p->next[t[i]-'a']);
        int k = t[i] - 'a';
        p=p->next[k];p->val++;
    }
    // puts("OUT");
}

void topo(){
    for(node *i=root;i<ext;i++) if(!i->deg) Q.push(i);
    while(!Q.empty()){
        node *p=Q.front();Q.pop();ans[p->word]=p->val;
        // printf("p:%ld\n",p-root);
        if(p!=root){
            p->fail->val += p->val;
            if(--p->fail->deg==0) Q.push(p->fail);
        }
    }
}

int main() {
    int n;scanf("%d", &n);root=Ot();
    for (int i = 1;i <= n;i++) {
        scanf("%s", word);
        insert(i);
    }
    build_fail();
    scanf("%s", t);
    query();topo();
    for (int i = 1;i <= n;i++) {
        cout<<ans[num[i]]<<endl;
    }
    return 0;
}

本文标题:AC自动机的学习

文章作者:xia0ji233

发布时间:2022-04-02, 13:00:00

最后更新:2022-12-26, 18:51:30

原始链接:http://example.com/2022/04/02/AC%E8%87%AA%E5%8A%A8%E6%9C%BA%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 题目1
    1. 1.1. 标程
  2. 2. 题目2
    1. 2.1. 标程
  3. 3. 题目3
    1. 3.1. 标程
|