AC自动机模板题 HDU - 2222

Keywords Search  HDU - 2222

贴个vj的链接https://vjudge.net/problem/HDU-2222

题意：T组数据，n个单词，再给你一个串，看有几个单词在这个串里面出现过

Sample Input

1

5

she

he

say

shr

her

yasherhs

Sample Output

3

#include <bits/stdc++.h>

#define ll long long

#define ull unsigned long long

using namespace std;

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3f;

const int N = 5e5 + 1000;

int fa[N], trie[N][30], tot, vis[N];

void build(string s){

    int len = s.size();

    int pos = 0;

    for(int i = 0; i < len; i++){

        int son = s[i] - 'a';

        if(!trie[pos][son]) trie[pos][son] = ++tot;

        pos = trie[pos][son];

    }

    vis[pos]++;

}

void getfail(){

    queue<int> q;

    for(int i = 0, p; i < 26; i++){

        p = trie[0][i];

        if(p){

            fa[p] = 0;

            q.push(p);

        }

    }

    while(q.size()){

        int now = q.front();

        q.pop();

        for(int i = 0; i < 26; i++){

            int u = trie[now][i];

            if(u){

                q.push(u);

                fa[u] = trie[fa[now]][i];

            }

            else trie[now][i] = trie[fa[now]][i];

        }

    }

}

int getans(string s){

    int now = 0, ans = 0;

    for(int i = 0; i < s.size(); i++){

        now = trie[now][s[i]-'a'];

        for(int j = now; j && vis[j]!=-1; j = fa[j]){

            ans+=vis[j];

            vis[j] = -1;

        }

    }

    return ans;

}

int main(){

    int t; cin >> t;

    fa[0] = 0;

    while(t--){

        memset(trie, 0, sizeof(trie));

        memset(vis, 0, sizeof(vis));

        tot = 0;

        int n; cin >> n;

        string s;

        for(int i = 1; i <= n; i++){

            cin >> s;

            build(s);

        }

        getfail();

        cin >> s;

        cout << getans(s) << endl;

    }

}

AC自动机模板题 HDU - 2222的相关教程结束。