UVa 1449 – Dominating Patterns [AC自动机]

点击打开uva题目链接

题意

有n个由小写字母组成的字符串和一个文本串T,你的任务是找出哪些字符串在文本中出现的次数最多。例如字符串aba在ababa中出现了2次,但字符串bab中只出现了1次。

分析

第一道AC自动机的题目,AC自动机一般适用于模板多长度短,文本串少而又长的情况。AC自动机是字典树和KMP的结合。代码仿照刘汝佳老师的代码修改,处理print函数即可符合各种题目要求。

C++代码

#include <bits/stdc++.h>
using namespace std;

int n;
char txt[1000010], pat[155][77];

struct ACAutomate {
    static const int maxnode = 12000, sigma_size = 26;
    int ch[maxnode][sigma_size], val[maxnode], cnt[maxnode], sz;
    int f[maxnode], last[maxnode];

    ACAutomate() { clear(); }
    void clear() {
        sz = 1; memset(ch[0], 0, sizeof(ch[0])); val[0] = 0;
        memset(cnt, 0, sizeof(cnt));
    }

    int idx(char x) { return x - 'a'; }
    void insert(const char *s, int v) {
        int u = 0;
        for(int i = 0; s[i]; ++i) {
            int id = idx(s[i]);
            if(!ch[u][id]) {
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz] = 0;
                ch[u][id] = sz++;
            }
            u = ch[u][id];
        }
        val[u] = v;
    }


    void print(int j) {
        while(j) {
            if(val[j]) ++cnt[val[j]];
            j = last[j];
        }
    }

    void find(const char *T) {
        int j = 0;
        for(int i = 0; T[i]; ++i) {
            int c = idx(T[i]);
            while(j && !ch[j]) j = f[j];
            j = ch[j];
            print(j);
        }
    }

    void getFail() {
        queue<int> qu;
        f[0] = 0;
        for(int c = 0; c < sigma_size; ++c) {
            int u = ch[0];
            if(u) { f[u] = 0; qu.push(u); last[u] = 0; }
        }
        while(!qu.empty()) {
            int r = qu.front(); qu.pop();
            for(int c = 0; c < sigma_size; ++c) {
                int u = ch[r];
                if(!u) continue;
                qu.push(u);
                int v = f[r];
                while(v && !ch[v]) v = f[v];
                f[u] = ch[v];
                last[u] = val[f[u]] ? f[u] : last[f[u]];
            }
        }
    }
}ac;



int main() {
    // freopen("/home/kun/buffer/in", "r", stdin);
    while(scanf("%d", &n), n) {
        ac.clear();
        for (int i = 1; i <= n; ++i) {
            scanf("%s", pat[i]);
            ac.insert(pat[i], i);
        }
        ac.getFail();

        scanf("%s", txt);
        ac.find(txt);
        int best = -1;
        for(int i = 1; i <= n; ++i)
            best = max(best, ac.cnt[i]);
        printf("%d\n", best);
        for(int i = 1; i <= n; ++i)
            if(ac.cnt[i] == best)
                printf("%s\n", pat[i]);
    }
    return 0;
}

欢迎留言