社区讨论

本地跑两个数据点都对,但提交究极神秘RE,萌新求助!!

P3808AC 自动机(简单版)参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@ly0ywjgo
此快照首次捕获于
2024/06/30 11:04
2 年前
此快照最后确认于
2024/06/30 15:10
2 年前
查看原帖
两个RE的测试点,本地跑都是对的,但是交上去就是RE。
CPP
#include<bits/stdc++.h>

#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...) 42
#endif

using i64 = long long;

namespace ranges = std::ranges;

struct AhoCorasick {
    static constexpr int ALPHABET = 26;
    struct Node {
        int len;
        int link;
        int end_cnt;//多维护一个以当前endtag的字符串个数,因为可能重复
        std::array<int, ALPHABET> next;
        Node() : len{0}, link{0}, next{}, end_cnt{} {}
    };
    
    std::vector<Node> t;
    
    AhoCorasick() {
        init();
    }
    
    void init() {
        t.assign(2, Node());
        t[0].next.fill(1);
        t[0].len = -1;
    }
    
    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }
    
    int add(const std::string &a) {
        int p = 1;
        for (auto c : a) {
            int x = c - 'a';
            if (t[p].next[x] == 0) {
                t[p].next[x] = newNode();
                t[t[p].next[x]].len = t[p].len + 1;
            }
            p = t[p].next[x];
        }
        t[p].end_cnt += 1;
        return p;
    }
    
    void work() {
        std::queue<int> q;
        q.push(1);
        
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            
            for (int i = 0; i < ALPHABET; i++) {
                if (t[x].next[i] == 0) {
                    t[x].next[i] = t[t[x].link].next[i];
                } else {
                    t[t[x].next[i]].link = t[t[x].link].next[i];
                    q.push(t[x].next[i]);
                }
            }
        }
    }
    
    int next(int p, int x) {
        return t[p].next[x];
    }
    
    int link(int p) {
        return t[p].link;
    }

    int cnt(int p) {
        return t[p].end_cnt;
    }

    int reset_cnt(int p) {
        t[p].end_cnt = 0;
    }
    
    int len(int p) {
        return t[p].len;
    }
    
    int size() {
        return t.size();
    }
};

signed main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n; std::cin >> n;
    std::vector<std::string> patterns(n); for (auto& x : patterns) {std::cin >> x;}
    std::string text; std::cin >> text;

    AhoCorasick ac; for (auto& str : patterns) {ac.add(str);} ac.work();
    
    int ans{}, now{1};
    
    for (auto& c : text) {
        now = ac.next(now, c - 'a');
        for (int p = now; p != 0 and ac.cnt(p) != 0; p = ac.link(p)) {
            ans += ac.cnt(p); ac.reset_cnt(p);
        } 
    }

    std::cout << ans << '\n';

    return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...