社区讨论
关于gets()
题目总版参与者 9已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @locp3di4
- 此快照首次捕获于
- 2023/10/30 17:26 2 年前
- 此快照最后确认于
- 2023/11/05 04:19 2 年前
- 据说 读大字符数组是比 与解绑后的 快,为何并没有人在诸如P3375 【模板】KMP字符串匹配、P5357 【模板】AC自动机(二次加强版)中使用?
(导致我想抄也没得抄)
#include <bits/stdc++.h>
using namespace std;
int trie[200010][26], fail[200010], res[200010], id[200010], que[200010], tot, len, n, a, b(1);
char s[2000010];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> s + 1; //->gets(s + 1);
len = strlen(s + 1);
for (int j = 1; j <= len; ++j) {
int ch = s[j] - 'a';
if (!trie[id[i]][ch]) trie[id[i]][ch] = ++tot;
id[i] = trie[id[i]][ch];
//cout<<"id["<<i<<"] = "<<id[i]<<endl;
}
}
for (int i = 0; i < 26; ++i) if (trie[0][i]) que[++a] = trie[0][i];
while (b <= a) {
int u = que[b++];
for (int i = 0; i < 26; ++i) {
if (trie[u][i]) {
fail[trie[u][i]] = trie[fail[u]][i];
que[++a] = trie[u][i];
} else trie[u][i] = trie[fail[u]][i];
}
}
cin >> s + 1; //->gets(s + 1);
len = strlen(s + 1);
//printf("%s %d\n",s+1,len);
for (int i = 1, p = 0; i <= len; ++i) {
int ch = s[i] - 'a';
p = trie[p][ch];
res[p]++;
}
for (int i = tot; i >= 1; --i) res[fail[que[i]]] += res[que[i]];
for (int i = 1; i <= n; ++i) cout << res[id[i]] << "\n";
}
回复
共 11 条回复,欢迎继续交流。
正在加载回复...