社区讨论
本地跑两个数据点都对,但提交究极神秘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 条回复,欢迎继续交流。
正在加载回复...