#2 WA 求调
查看原帖
#2 WA 求调
610557
shinzanmonoszm 妹妹楼主2023/3/16 22:45
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<queue>
const int sz = 1e6 + 10;
struct ACAM {
    struct node {
        int end, tree[128];
    } tree[sz];
    int fail[sz], lstnode = 1;
    void insert(std::string s) {
        int cur = 1;
        for (int i = 0; i < s.length(); i++) {
            if (tree[cur].tree[s[i]] == 0) 
                tree[cur].tree[s[i]] = ++lstnode;
            cur = tree[cur].tree[s[i]];
        }
        tree[cur].end++;
    }
    void buildFail() {
        std::queue<int> qq;
        for (char c = 'a'; c <= 'z'; c++) 
            if (tree[1].tree[c] != 0) qq.push(tree[1].tree[c]); 
        while (!qq.empty()) {
            int u = qq.front();
            qq.pop();
            for (char c = 'a'; c <= 'z'; c++) {
                if (tree[u].tree[c] != 0) 
                    fail[tree[u].tree[c]] = tree[fail[u]].tree[c], qq.push(tree[u].tree[c]);
                else tree[u].tree[c] = tree[fail[u]].tree[c];
            }
        }
    }
    int query(std::string s) {
        int cur = 1, res = 0;
        for (int i = 0; i < s.length(); i++) {
            cur = tree[cur].tree[s[i]];
            for (int j = cur; j != 0 && tree[j].end != -1; j = fail[j]) 
                res += tree[j].end, tree[j].end = -1;
        }
        return res;
    }
} ac;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::string s;
    std::cin >> n;
    for (int i = 1; i <= n; i++) 
        std::cin >> s, ac.insert(s);
    ac.buildFail();
    std::cin >> s;
    std::cout << ac.query(s) << "\n";
    return 0;
}
2023/3/16 22:45
加载中...