#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e4 * 55, M = 26;

class Aho_Corasick{
int son[N][M], idx, cnt[N], ne[N];
queue <int> que;
public:
    Aho_Corasick() : idx(0) {
        memset(son, 0, sizeof son);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
    }
    void insert(string& s) {
        int p = 0;
        for (const char& ch : s) {
            int u = ch - 'a';
            if (!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
        }
        ++cnt[p];
    }
    void kmp() {
        for (int i = 0; i < M; ++i)
            if (son[0][i]) que.push(son[0][i]);
        while(que.size()) {
            int t = que.front(); que.pop();
            for (int i = 0; i < M; ++i) {
                int c = son[t][i];
                if (!c) continue;
                que.push(c);
                int j = ne[t];
                while(j && !son[j][i]) j = ne[j];
                if (son[j][i]) j = son[j][i];
                ne[c] = j;
            }
        }
    }
    int query(string& s) {
        int res = 0;
        for (int i = 0, j = 0; i < s.length(); ++i) {
            int u = s[i] - 'a';
            while(j && !son[j][u]) j = ne[j];
            if (son[j][u]) j = son[j][u];
            int p = j;
            while(p) {
                res += cnt[p];
                cnt[p] = 0;
                p = ne[p];
            }
        }
        return res;
    }
};
int t, n;
string s;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) {
        Aho_Corasick ac;
        cin >> n;
        while(n--) {
            cin >> s;
            ac.insert(s);
        }
        cin >> s;
        ac.kmp();
        cout << ac.query(s) << '\n';
    }
    return 0;
} 

Trie Graph

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e4 * 55, M = 26;

class Aho_Corasick{
int son[N][M], idx, cnt[N], ne[N];
queue <int> que;
public:
    Aho_Corasick() : idx(0) {
        memset(son, 0, sizeof son);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
    }
    void insert(string& s) {
        int p = 0;
        for (const char& ch : s) {
            int u = ch - 'a';
            if (!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
        }
        ++cnt[p];
    }
    void kmp() {
        for (int i = 0; i < M; ++i)
            if (son[0][i]) que.push(son[0][i]);
        while(que.size()) {
            int t = que.front(); que.pop();
            for (int i = 0; i < M; ++i) {
                int c = son[t][i];
                if (!c) son[t][i] = son[ne[t]][i];
                else {
                    ne[c] = son[ne[t]][i];
                    que.push(c);
                }
            }
        }
    }
    int query(string& s) {
        int res = 0;
        for (int i = 0, j = 0; i < s.length(); ++i) {
            int u = s[i] - 'a';
            j = son[j][u];
            int p = j;
            while(p) {
                res += cnt[p];
                cnt[p] = 0;
                p = ne[p];
            }
        }
        return res;
    }
};
int t, n;
string s;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) {
        Aho_Corasick ac;
        cin >> n;
        while(n--) {
            cin >> s;
            ac.insert(s);
        }
        cin >> s;
        ac.kmp();
        cout << ac.query(s) << '\n';
    }
    return 0;
} 

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status