题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2222

题目大意

给你一堆关键字,以及需要搜索的字符串s,求在s中出现了多少个关键字。

思路

AC自动机入门题,这里给出动态版和静态版,动态版比较快但是没优化,写起来有点烦,还是用静态版吧,参考Kuangbin模板。

AC代码(动态版)

/*************************************************************************
    > File Name: 2222.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-10-24 六 21:44:40 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int T;
int N;
char s[1000005];

struct Trie {
    int cnt; // 单词结尾节点统计单词个数
    Trie *fail; // 跳转指针fail
    Trie *next[26]; // 存放26个字母
    Trie() {
        cnt = 0; // 初始化
        fail = NULL;
        memset(next, 0, sizeof(next));
    }
} *root;

void insert(const char *s) { // 插入单词,构建Trie树
    Trie *p = root;
    int len = strlen(s);
    for(int i=0; i<len; ++i) {
        int id = s[i] - 'a';
        if(!p->next[id])
            p->next[id] = new Trie();
        p = p->next[id];
    }
    ++p->cnt;
}

void build_AC() { // 第一个节点指向根节点
    Trie *p, *temp;
    queue<Trie*> que;
    que.push(root); // BFS建树
    while(!que.empty()) {
        p = que.front(); que.pop(); // 从根节点开始构建
        for(int i=0; i<26; ++i) {
            if(p->next[i]) {// 该节点后面有节点
                if(p == root) // 如果该节点是根节点,则后继节点为第一个子节点,fail指向根节点
                    p->next[i]->fail = root;
                else { // 普通节点
                    temp = p->fail;
                    while(temp) { // 若p的跳转指针未指向根
                        if(temp->next[i]) { // 如果跳转后的后继节点和p的后继节点一样,则p的后继节点fail指向跳转后的后继节点
                            p->next[i]->fail = temp->next[i];
                            break;
                        }
                        else
                            temp = temp->fail; // 继续跳转
                    }
                    if(!temp) // 若跳转到根节点,则后继节点fail指向根节点
                        p->next[i]->fail = root;
                }
                que.push(p->next[i]); // 后继节点入队
            }
        }
    }
}

int match(const char *s) {
    int res = 0;
    int len = strlen(s);
    Trie *p = root, *temp;
    for(int i=0; i<len; ++i) {
        int id = s[i] - 'a';
        while(!p->next[id] && p != root) p = p->fail; // 失配跳转
        p = p->next[id];
        if(!p) p=root; // 再次失配,跳转回根节点
        temp = p;
        while(temp != root && temp->cnt != -1) {
            res += temp->cnt; // 累加
            temp->cnt = -1; // 标记为已搜索过的节点,以防重复累加
            temp = temp->fail;
        }
    }
    return res;
}

void freeTrie(Trie *p) { // 释放AC自动机
    for(int i=0; i<26; ++i) if(p->next[i]) freeTrie(p->next[i]);
    delete p;
}

void solve() {
    build_AC();
    cout << match(s) << endl;
    free(root);
}

int main()
{
#ifdef Oj
    freopen("2222.in", "r", stdin);
#endif
    cin.sync_with_stdio(false);
    cin >> T;
    char keyword[10005];
    while(T--) {
        root = new Trie();
        cin >> N;
        for(int i=0; i<N; ++i) {
            cin >> keyword;
            insert(keyword);
        }
        cin >> s;
        solve();
    }
    return 0;
}

AC代码(静态版)

/*************************************************************************
    > File Name: 2222_2.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-10-29 四 17:29:45 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

struct Trie {
    static const int max_L = 500010;
    static const int max_c = 26;
    int cnt[max_L]; // 单词结尾节点统计该单词个数
    int fail[max_L]; // fail指针
    int next[max_L][max_c];
    int root, L; // 根指针,当前最大有效节点指针
    int newnode() {
        for(int i=0; i<max_c;++i)
            next[L][i] = -1;
        cnt[L++] = 0;
        return L-1;
    }
    void init() {
        L = 0;
        root = newnode();
    }

    void insert(const char *s) { // 建立Trie树
        int len = strlen(s);
        int p = root;
        for(int i=0; i<len; ++i) {
            int id = s[i] - 'a';
            if(next[p][id] == -1) next[p][id] = newnode();
            p = next[p][id];
        }
        ++cnt[p];
    }

    void build() {
        queue<int> que;
        fail[root] = root; // 根fail指针指向根,避免多余的判断
        for(int i=0; i<max_c; ++i) // 处理root的后继节点,都指向root
            if(next[root][i] == -1) next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }

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

            for(int i=0; i<max_c; ++i)
                if(next[p][i] == -1) next[p][i] = next[fail[p]][i]; // 方便后面match失配的fail转移
                else {
                    fail[next[p][i]] = next[fail[p]][i];
                    que.push(next[p][i]);
                }
        }
    }

    int match(const char *s) {
        int len = strlen(s);
        int p = root;
        int res = 0;
        for(int i=0; i<len; ++i) {
            int id = s[i] - 'a';
            p = next[p][id];
            int tmp = p;
            while(tmp != root) {
                res += cnt[tmp];
                cnt[tmp] = 0;
                tmp = fail[tmp];
            }
        }
        return res;
    }

};

int T, n;
char s[1000005];
Trie ac;

void solve() {
    ac.build();
    cout << ac.match(s) << endl;
}

int main()
{
#ifdef Oj
    freopen("2222.in", "r", stdin);
#endif
    // cin.sync_with_stdio(false);
    // cin >> T;
    scanf("%d", &T);
    char in[55];
    while(T--) {
        ac.init();
        // cin >> n;
        scanf("%d", &n);
        for(int i=0; i<n; ++i) {
            // cin >> in;
            scanf("%s", in);
            ac.insert(in);
        }
        // cin >> s;
        scanf("%s", s);
        solve();
    }
    return 0;
}