首页 > 其他 > 详细

ac自动机

时间:2018-06-23 12:47:06      阅读:176      评论:0      收藏:0      [点我收藏+]

给定n个模式串和1个文本串,求有多少个模式串在文本串里出现过。

#include <bits/stdc++.h>
const int maxn = 3*1e6+5, M = 1e6+7;
using namespace std;
int siz, cur[maxn];
bool flag[maxn];
struct ac{
    struct Sta{
        int son[26], fail;
        int cnt, rr;
    }sta[maxn];
    void init(){
        siz = 1;
    }
    void insert(char *S, int tot){
        int len = strlen(S);
        int now = 0;

        for(int i = 0; i < len; i++){
            char c = S[i];
            if(sta[now].son[c-a] == 0)
                sta[now].son[c-a] = siz++;
            now = sta[now].son[c-a];
        }
        sta[now].cnt++;
    };

    void build(){
        queue <int> Q;

        Q.push(0);

        while(!Q.empty()){
            int u = Q.front(); Q.pop();
            for(int i = 0; i < 26; i++){
                if(sta[u].son[i]){
                    if(u == 0)sta[sta[u].son[i]].fail = 0;
                    else 
                        sta[sta[u].son[i]].fail = sta[sta[u].fail].son[i]; 
                    Q.push(sta[u].son[i]);
                }
                else sta[u].son[i] = sta[sta[u].fail].son[i];
            }
        }
    }

    int match(char *S){
        int now = 0, res = 0;
        int len = strlen(S);
        for(int i = 0; i < len; i++){
            char c = S[i];
            now = sta[now].son[c - a];
            for(int t = now; t && !flag[t]; t = sta[t].fail)
                res += sta[t].cnt, flag[t] = 1;
        }
        return res;
    }
    int Query(int t){
        return sta[cur[t]].rr;
    }

}Tr;
char a[maxn][55];
char s[M];
char S[M];
int main()
{
    int n ,m;
    scanf("%d", &n);
    Tr.init();
    for(int i = 1; i <= n; i++){
       // scanf("\n");
        scanf("%s", s);
        Tr.insert(s, i);
    }
    Tr.build();
   // scanf("\n");
    scanf("%s", S);
    printf("%d\n", Tr.match(S));
    return 0;
}

有 NN 个由小写字母组成的模式串以及一个文本串 TT 。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 TT 中出现的次数最多。

#include <bits/stdc++.h>
const int maxn = 3*1e6+5, M = 1e6+7;
using namespace std;
int siz;
bool flag[maxn];
struct Result{
    int sum , id;
}ans[M];
struct ac{
    struct Sta{
        int son[26], fail;
        int end, rr;
    }sta[maxn];
    void clear(int x){
        memset(sta[x].son, 0, sizeof(sta[x].son));
        sta[x].end = sta[x].fail = 0;
    }
    void insert(char *S, int tot){
        int len = strlen(S);
        int now = 0;

        for(int i = 0; i < len; i++){
            char c = S[i];
            if(sta[now].son[c-a] == 0){
                sta[now].son[c-a] = ++siz;
                clear(siz);
            }    
            now = sta[now].son[c-a]; 
        }
        sta[now].end = tot;
    };

    void build(){
        queue <int> Q;

        Q.push(0);

        while(!Q.empty()){
            int u = Q.front(); Q.pop();
            for(int i = 0; i < 26; i++){
                if(sta[u].son[i]){
                    if(u == 0)sta[sta[u].son[i]].fail = 0;
                    else 
                        sta[sta[u].son[i]].fail = sta[sta[u].fail].son[i]; 
                    Q.push(sta[u].son[i]);
                }
                else sta[u].son[i] = sta[sta[u].fail].son[i];
            }
        }
    }

    void match(char *S){
        int now = 0, res = 0;
        int len = strlen(S);
        for(int i = 0; i < len; i++){
            char c = S[i];
            now = sta[now].son[c - a];
            for(int t = now; t; t = sta[t].fail)
                ans[sta[t].end].sum++;
        }
    }
}Tr;
char a[M][75];
char S[M];
bool cmp(Result a, Result b){
    return a.sum == b.sum ? a.id < b.id : a.sum > b.sum;
}
int main()
{
    int n ,m;
    while(scanf("%d", &n) == 1){
        if(!n)break;
        siz = 0;
        for(int i = 1; i <= n; i++){
            ans[i].id = i;
            ans[i].sum = 0;
        }
        Tr.clear(0);
        for(int i = 1; i <= n; i++){
            scanf("%s", a[i]);
            Tr.insert(a[i], i);
        }
        Tr.build();
        scanf("%s", S);
        Tr.match(S);
        sort(ans+1, ans+1+n, cmp);
        printf("%d\n", ans[1].sum);
        for(int i = 1; i <= n; i++){
            if(ans[i].sum < ans[1].sum)break;
            printf("%s\n", a[ans[i].id]);
        }    
    }
    
    return 0;
}

 

ac自动机

原文:https://www.cnblogs.com/EdSheeran/p/9216762.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!