社区讨论
#2WA求调
P3808AC 自动机(简单版)参与者 6已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @lo2xhvhp
- 此快照首次捕获于
- 2023/10/23 21:23 2 年前
- 此快照最后确认于
- 2023/10/23 21:23 2 年前
rt
CPP#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 0721;
int tr[N][26], ed[N], fail[N], tot;
void insert(string s) {
int u = 0;
for (int i = 0; i < s.length(); ++i) {
if (!tr[u][s[i] - 'a'])
tr[u][s[i] - 'a'] = ++tot;
u = tr[u][s[i] - 'a'];
}
++ed[u];
}
queue<int> q;
void build(void) {
for (int i = 0; i < 26; ++i) {
if (tr[0][i]) q.push(tr[0][i]);
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; ++i) {
if (tr[u][i]) {
fail[tr[u][i]] = tr[fail[u]][i];
q.push(tr[u][i]);
} else
tr[u][i] = tr[fail[u]][i];
}
}
}
int query(string s) {
int res = 0, u = 0;
for (int i = 0; i < s.length(); ++i) {
u = tr[u][s[i] - 'a'];
for (int j = u; j && ed[j] != -1; j = fail[j]) {
res += ed[j];
ed[j] = -1;
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
string s;
cin >> s;
insert(s);
}
string s;
cin >> s;
cout << query(s);
return 0;
}
回复
共 6 条回复,欢迎继续交流。
正在加载回复...