hdu 2222

hdu 2222 AC 自动机
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2222

#include <stdio.h>

#define N 500051
#define CHARSET_SIZE 26
#define NIL 0
#define ROOT 1

int alloc;
int trans[N][CHARSET_SIZE];
int fails[N];
int counts[N];

int qhead, qtail;
int queue[N];

char str[1000001];
char keyword[51];

int ac_alloc() {
    int n = alloc++;
    for (int c = 0; c < CHARSET_SIZE; c++) {
        trans[n][c] = NIL;
    }
    counts[n] = 0;
    return n;
}

void ac_insert(char *s) {
    int n = ROOT;
    for (int i = 0; s[i]; i++) {
        int c = s[i] - 'a';
        if (trans[n][c] == NIL) {
            trans[n][c] = ac_alloc();
        }
        n = trans[n][c];
    }
    counts[n]++;
}

void ac_build_fails() {
    qhead = qtail = 0;
    fails[ROOT] = NIL;
    for (int i = 0; i < CHARSET_SIZE; i++) {
        if (trans[ROOT][i] != NIL) {
            fails[trans[ROOT][i]] = ROOT;
            queue[qtail++] = trans[ROOT][i];
        }
    }
    while (qhead < qtail) {
        int n = queue[qhead++];
        for (int i = 0; i < CHARSET_SIZE; i++) {
            if (trans[n][i] == NIL) {
                continue;
            }
            int fail = fails[n];
            while (fail != NIL) {
                if (trans[fail][i] != NIL) {
                    fails[trans[n][i]] = trans[fail][i];
                    break;
                }
                fail = fails[fail];
            }
            if (fail == NIL) {
                fails[trans[n][i]] = ROOT;
            }
            queue[qtail++] = trans[n][i];
        }
    }
}

int ac_match(char *s) {
    int total = 0;
    int n = ROOT;
    for (int i = 0; s[i]; i++) {
        int c = s[i] - 'a';
        while (trans[n][c] == NIL && n != ROOT) {
            n = fails[n];
        }
        n = trans[n][c];
        if (n == NIL) {
            n = ROOT;
        }
        int t = n;
        while (t != ROOT && counts[t] != -1) {
            total += counts[t];
            counts[t] = -1;
            t = fails[t];
        }
    }
    return total;
}

int main() {
    int t;

    scanf("%d", &t);
    while (t--) {
        alloc = ROOT;
        ac_alloc();
        int w;
        scanf("%d", &w);
        while (w--) {
            scanf("%s", keyword);
            ac_insert(keyword);
        }
        ac_build_fails();
        scanf("%s", str);
        printf("%d\n", ac_match(str));
    }
    return 0;
}

标签: none

添加新评论