A Huster

0%

AC自动机

Posted on Valine:

先存代码

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
49
#include<bits/stdc++.h>
#define maxn 1000007
using namespace std;
int n,ans;
int tr[maxn][28],val[maxn],cnt,fail[maxn];
char mod[maxn],tx[maxn];
queue<int >q;

void build(char *a){
    int now=0;
    for(int i=0;a[i];i++){
        if(!tr[now][a[i]-'a']) tr[now][a[i]-'a']=++cnt;
        now=tr[now][a[i]-'a'];
    }
    val[now]++;
}//建树 

void AC(){
    for(int i=0;i<26;i++) if(tr[0][i]) q.push(tr[0][i]);//26个字母跑 
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<26;i++){
            if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);//调取指针 
            else tr[u][i]=tr[fail[u]][i];//建立“虚边”——指向失配指针的i边
            //这里已经改变了trie图 
        }
    }
}

int query(char *t){
    int ol=0,u=0;
    for(int i=0;t[i];i++){
        u=tr[u][t[i]-'a'];
        for(int j=u;j&&val[j]!=-1;j=fail[j])
            ol+=val[j],val[j]=-1;//fail跳（这样其实很慢） 
    }
    return ol;
}

int main(){
//    freopen("cin.in","r",stdin);
//    freopen("co.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%s",mod),build(mod);
    AC();
    scanf("%s",tx);ans=query(tx);
    printf("%d\n",ans);
}

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
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
#define maxn 1000007
using namespace std;
int T,n,ans;
char mod[maxn][100],tx[maxn];

namespace AC{
    int tr[maxn][27],fail[maxn],tot;
    int cnt,val[maxn],num[maxn];
    void Init(){
        memset(tr,0,sizeof(tr));
        memset(num,0,sizeof(num));
        memset(fail,0,sizeof fail);
        memset(val,0,sizeof val);
        cnt=ans=0;
    }
    void insert(char *s,int id){
        int now=0;
        for(int i=0;s[i];i++){
            if(!tr[now][s[i]-'a']) tr[now][s[i]-'a']=++cnt;
            now=tr[now][s[i]-'a'];
        }
        val[now]=id;//记录id，这个不怕覆盖 
    }
    queue<int >q;
    void build(){
        for(int i=0;i<26;i++) if(tr[0][i]) q.push(tr[0][i]);
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=0;i<26;i++)
                if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]),cerr<<fail[tr[u][i]]<<endl;
                else tr[u][i]=tr[fail[u]][i];
        }
    }
    void query(char *t){
        int u=0;
        for(int i=0;t[i];i++){
            u=tr[u][t[i]-'a'];
            for(int j=u;j;j=fail[j])
                if(val[j]) num[val[j]]++,ans=max(ans,num[val[j]]);
        }//还是跳，不过记录的不一样而已 
        printf("%d\n",ans);
        for(int i=1;i<=n;i++) if(ans==num[i]) printf("%s\n",mod[i]);
    }
}

int main(){
    scanf("%d",&n);
    while(n){
        AC::Init();
        for(int i=1;i<=n;i++) scanf("%s",mod[i]),AC::insert(mod[i],i);
        AC::build();
        scanf("%s",tx);
        AC::query(tx);
        scanf("%d",&n);
    }
}

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
49
50
51
52
53
#include<bits/stdc++.h>
#define maxn 2000007
using namespace std;
int n;
char mod[maxn],tx[maxn];
int fail[maxn],tr[maxn][27],val[maxn],num[maxn];
int id[maxn],cnt,in[maxn],to[maxn];

void insert(char *a,int idx){
    int now=0;
    for(int i=0;a[i];i++){
        if(!tr[now][a[i]-'a']) tr[now][a[i]-'a']=++cnt;
        now=tr[now][a[i]-'a'];
    }
    val[now]++;id[idx]=now;//记录 
}

queue<int >q;

void build(){
    for(int i=0;i<26;i++) if(tr[0][i]) q.push(tr[0][i]);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<26;i++){
            if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]),in[fail[tr[u][i]]]++;
            else tr[u][i]=tr[fail[u]][i];
        }
    }
}

void query(char *t){
    int u=0;
    for(int i=0;t[i];i++)
        u=tr[u][t[i]-'a'],num[u]++;
}

void topu(){
    for(int i=1;i<=cnt;i++) if(!in[i]) q.push(i);
    while(!q.empty()){
        int u=q.front(),v=fail[u];q.pop();
        num[v]+=num[u];--in[v];
        if(!(in[v])) q.push(v);
    }
}//这里是跟题解学的topu,效率也挺高 

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%s",mod),insert(mod,i);
    build();
    scanf("%s",tx);query(tx);
    topu(); 
    for(int i=1;i<=n;i++) printf("%d\n",num[id[i]]);
}

单词

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
#include<bits/stdc++.h>
#define maxn 2000007
using namespace std;
int n;
char mod[maxn],tx[maxn],c[maxn];
int fail[maxn],tr[maxn][28],val[maxn],num[maxn];
int id[maxn],cnt,in[maxn],tot;

void insert(char *a,int idx){
    int now=0;
    for(int i=0;a[i];i++){
        if(!tr[now][a[i]-'a']) tr[now][a[i]-'a']=++cnt;
        now=tr[now][a[i]-'a'];
    }
    val[now]++;id[idx]=now;
}

queue<int >q;

void build(){
    for(int i=0;i<27;i++) if(tr[0][i]) q.push(tr[0][i]);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<27;i++){
            if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]),in[fail[tr[u][i]]]++;
            else tr[u][i]=tr[fail[u]][i];
        }
    }
}

void query(char *t){
    int u=0;
    for(int i=0;t[i];i++)
        u=tr[u][t[i]-'a'],num[u]++;
}

void topu(){
    for(int i=1;i<=cnt;i++) if(!in[i]) q.push(i);
    while(!q.empty()){
        int u=q.front(),v=fail[u];q.pop();
        num[v]+=num[u];--in[v];
        if(!(in[v])) q.push(v);
    }
}

void work(char *a,char *b){
    int len1=strlen(a),len2=strlen(b);
    for(int i=len1;i<len1+len2;i++)
        a[i]=b[i-len1];
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%s",c),work(mod,c),
        tot=strlen(mod),insert(c,i),mod[tot++]='{';
    build();
    query(mod);topu();
    for(int i=1;i<=n;i++) printf("%d\n",num[id[i]]);
}
本站访问次数：