点击打开hdu题目链接

题意

给你n个单词和一个字符串,问你有几个单词在字符串中出现过

分析

AC自动机的模板题,灵活构造修改模板即可。

C++代码

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

struct ACAutomate {
    static const int maxnode = 500050, sigma_size = 26;
    int ch[maxnode][sigma_size], val[maxnode], sz;
    int f[maxnode], last[maxnode];
    ACAutomate() { clear(); }
    void clear() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); val[0] = 0; }
    int idx(char x) { return x - 'a'; }
    void insert(const char *s) {
        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];
    }
    int print(int j) {
        int res = 0;
        while(j) {
            res += val[j];
            val[j] = 0;
            j = last[j];
        }
        return res;
    }
    int find(const char *T) {
        int j = 0, res = 0;
        for(int i = 0; T[i]; ++i) {
            int c = idx(T[i]);
            while(j && !ch[j]) j = f[j];
            j = ch[j];
            res += print(j);
        }
        return res;
    }
    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;

char buf[1000010];

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        int n; scanf("%d", &n);
        ac.clear();
        for(int i = 1; i <= n; ++i) {
            scanf("%s", buf);
            ac.insert(buf);
        }
        ac.getFail();
        scanf("%s", buf);
        printf("%d\n", ac.find(buf));
    }
    return 0;
}

欢迎留言