程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 1449 - Dominating Patterns(AC自動機)

uva 1449 - Dominating Patterns(AC自動機)

編輯：C++入門知識

uva 1449 - Dominating Patterns(AC自動機)

題目練級：uva 1449 - Dominating Patterns

題目大意：有一個由小寫字母組成的字符串集和一個文本T，要求找出那些字符串在文本中出現的次數最多。

解題思路：將字符串集建立AC自動機，然後傳入T進行匹配，對每個匹配上的字符串多應次數加1，最後找出最大值。出現次數與最大值相同的字符串輸出。注意字符集中出現相同字符的情況。

#include 
#include 
#include 
#include 
#include
#include 

using namespace std;

const int maxn = 155;
const int maxl = 100;
const int maxt = 1e6+5;
const int sigma_size = 26;
const int noden = maxn * maxl;

char str[maxt], word[maxn][maxl];
map ms;
int N, c[maxn];
int sz, ac[noden][sigma_size], val[noden];
int fail[noden], last[noden];

void insert (int x, char* s) {
    int u = 0, n = strlen(s);

    for (int i = 0; i < n; i++) {
        int v = s[i] - 'a';
        if (ac[u][v] == 0) {
            memset(ac[sz], 0, sizeof(ac[sz]));
            val[sz] = 0;
            ac[u][v] = sz++;
        }
        u = ac[u][v];
    }
    val[u] = x;
}

void get_fail () {
    queue que;
    fail[0] = 0;

    for (int i = 0; i < sigma_size; i++) {
        int u = ac[0][i];
        if (u) {
            fail[u] = last[u] = 0;
            que.push(u);
        }
    }

    while (!que.empty()) {
        int r = que.front();
        que.pop();

        for (int i = 0; i < sigma_size; i++) {
            int u = ac[r][i];

            if (u == 0) {
                ac[r][i] = ac[fail[r]][i];
                continue;
            }

            que.push(u);
            int v = fail[r];
            while (v && !ac[v][i])
                v = fail[v];

            fail[u] = ac[v][i];
            last[u] = val[fail[u]] ? fail[u] : last[fail[u]];
        }
    }
}

void count (int x) {
    if (x) {
        c[val[x]]++;
        count(last[x]);
    }
}

void find (char* T) {
    int u = 0;
    int n = strlen(T);

    for (int i = 0; i < n; i++) {
        int v = T[i] - 'a';
        /*
        while (u && !ac[u][v])
            u = fail[u];
            */
        u = ac[u][v];
        if (val[u])
            count(u);
        else
            count(last[u]);
    }
}

void init () {
    sz = 1;
    ms.clear();
    memset(ac[0], 0, sizeof(ac[0]));

    for (int i = 1; i <= N; i++) {
        scanf("%s", word[i]);
        insert(i, word[i]);
        ms[string(word[i])] = i;
    }

    memset(c, 0, sizeof(c));
    get_fail();
}

int main () {
    while (scanf("%d", &N) == 1 && N) {
        init();
        scanf("%s", str);
        find(str);

        int ans = -1;
        for (int i = 1; i <= N; i++)
            ans = max(ans, c[i]);
        printf("%d\n", ans);
        for (int i = 1; i <= N; i++) {
            if (c[ms[string(word[i])]] == ans)
                printf("%s\n", word[i]);
        }
    }
    return 0;
}