ababaaabbbbbbbaabaaaaababababbaaabbaabaabaabaaabbaaababbbabbaababbaabbababbaabbaaabbabbbaaaabaabbbaa
<2000107 bytes omitted>用户输出
0
系统信息
Exited with return code 0| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #20662 | #1059. 1-07E. JM的模板题 | Accepted | 100 | 5976 ms | 138580 K | C++ 11 / 2.7 K | JM233333 | 2019-07-29 21:09:18 |
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int SIZE = 26;
class Trie {
public:
bool existed;
int next[SIZE];
int fail;
int match;
};
void insert(char* s, int id);
void build();
void search(char* s);
void add_edge(int u, int v);
void dfs(int index);
const int MAX = 1e6 + 5;
Trie trtree[MAX];
Trie* const trie = trtree + 1;
int trcnt;
char S[MAX], Ti[MAX];
vector<int> graph[MAX];
int record[MAX], res[MAX];
int main() {
// freopen("test.txt", "r", stdin);
int n;
while (scanf("%s", S) != EOF) {
// 初始化
memset(trtree, 0, 2 * sizeof(Trie));
trie[0].fail = -1;
trcnt = 0;
for (int i = 0; i < MAX; i++) {
graph[i].clear();
}
memset(record, 0, sizeof(record));
memset(res, 0, sizeof(res));
// 输入
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", Ti);
insert(Ti, i);
}
// 建立自动机
build();
// 匹配自动机
search(S);
// DFS
dfs(0);
// 求和
ll sum = 0;
for (int i = 1; i <= n; i++) {
sum += res[record[i]];
}
// 输出
printf("%lld\n", sum);
}
return 0;
}
// 字典树：插入
void insert(char* s, int id) {
// 主循环
int index = 0;
for (int i = 0; s[i] != '\0'; i++) {
// 获取子节点
int& pos = trie[index].next[s[i] - 'a'];
// 插入
if (!pos) {
pos = ++trcnt;
memset(&trie[pos], 0, sizeof(Trie));
}
// 递进
index = pos;
}
// 计数
trie[index].existed = true;
record[id] = index;
}
// AC自动机：建立
void build() {
// BFS
queue<int> q;
q.push(0);
while (!q.empty()) {
// 出队
int t = q.front();
q.pop();
// 遍历字符集
for (int i = 0; i < SIZE; i++) {
// 获取子节点
int& pos = trie[t].next[i];
// 更新位置信息
if (!pos) {
pos = trie[trie[t].fail].next[i];
} else {
// 入队
q.push(pos);
// 标记
trie[pos].fail = trie[trie[t].fail].next[i];
trie[pos].match = (trie[pos].existed ? pos : trie[trie[pos].fail].match);
// 建图
add_edge(trie[trie[pos].fail].match, pos);
}
}
}
}
// AC自动机：查找
void search(char* s) {
// 主循环
int index = 0;
for (int i = 0; s[i] != '\0'; i++) {
// 递进
index = trie[index].next[s[i] - 'a'];
// 记录最长匹配
int tmp = trie[index].match;
if (trie[tmp].existed) {
res[tmp]++;
}
}
}
// 加入新边
inline void add_edge(int u, int v) { graph[u].push_back(v); }
// 深度优先搜索
void dfs(int u) {
for (int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
dfs(v);
if (trie[u].existed && trie[v].existed) {
res[u] += res[v];
}
}
}
ababaaabbbbbbbaabaaaaababababbaaabbaabaabaabaaabbaaababbbabbaababbaabbababbaabbaaabbabbbaaaabaabbbaa
<2000107 bytes omitted>用户输出
0
系统信息
Exited with return code 0bbaaaabaaaabbbbaaabbbbabbaaabaaabbbbbaaabababaabbbaaabbabaaaababaaabababbabaaababbbabbabababaaaababb
<2000107 bytes omitted>用户输出
0
系统信息
Exited with return code 0ababbbaaaababbababaaabbbbabbaabaabbaaababbabbbaaaaaabababbbbabaababaabaaaaaabbbabbabbbbbbbbabbababba
<2000107 bytes omitted>用户输出
0
系统信息
Exited with return code 0bbbbbabbaaabbaaabbabbbabbbabbabaaababbaaabaaabababbaaaabbaaabbbbbbbabbabaabbaabbabababaaaaababbabaaa
<2000107 bytes omitted>用户输出
0
系统信息
Exited with return code 0abaaaaaabbaaaaabaabaabbaaaaabbbbbaababbaaabbaaababbbbaaaaaaaaaaabaababbabbbbaaaaababbbbbbaabbbbabbab
<2000107 bytes omitted>用户输出
0
系统信息
Exited with return code 0babbbbbabbaabbbbabbbababbaaabaabaaabaabbaabbbabbbaaabbbabbbbbbbabbbabaabbbbabbbababaaaabbababaababaa
<2000107 bytes omitted>用户输出
0
系统信息
Exited with return code 0baaaaaaaaabaabbbbbbabababbaabaababbbaababbbbabaabababaabbabaabaabbaaaabaaabbabaabbbbbbabababbbbbbabb
<2000107 bytes omitted>用户输出
0
系统信息
Exited with return code 0baababbbbbbbbaaabbbbbbbbbabbaabbaaaaabababbbbbabbbababaaaaabababbbaababaaaabbbababababbaabbaabbabbab
<2000107 bytes omitted>用户输出
0
系统信息
Exited with return code 0abbbbaabbbbbaabbaaabaaabbbbabbbaaabbbbaaababbbbbbabbaaababaaaaaaabaabbbaaabbbaabbbabbbbabbbbbaababba
<2000107 bytes omitted>用户输出
0
系统信息
Exited with return code 0aaababbbaabbabaaaababbabaaabaabbaabbbbbbbaababbabbbaaababbaabbaaabbabababbaabaaabaaababaaaaaabbabbba
<2000107 bytes omitted>用户输出
0
系统信息
Exited with return code 0cbedbecbbaacaaedadbaaadebacdcdeaebdeaeccaeccedcddadcaeddadcedebeadeeebabeebadaeeccabaececebdabcdcbbe
<2199910 bytes omitted>用户输出
10266
系统信息
Exited with return code 0caacebdeebebecebcabecedeccdcacaaadeddaddbebeddecaddcebdeaababaebadbbebacdabccdcbdbabdadaeccdecbcccde
<2199910 bytes omitted>用户输出
10165
系统信息
Exited with return code 0ecacbcbaccbacdedebaebeabaaeabccbedaaceaaeabbbcbbacadbbadeceacbdbdebadcdabcdeeebaaedaaacacebbccecaddb
<2199910 bytes omitted>用户输出
10003
系统信息
Exited with return code 0dbcdaaebbadbddcebebbbcaabebbadbaeddeadcccddedbabcdbdeebbebbbdaecdadedcaaabedcecbdcdbadbeabeaebcceccb
<2199910 bytes omitted>用户输出
10297
系统信息
Exited with return code 0eddecaacdbacbedaaaecacecdaedbdcbcaeeddedaacbecbabcbababcbddbabbbaccebcbbecdadadcbeabbdadabbdecdeacee
<2199910 bytes omitted>用户输出
10355
系统信息
Exited with return code 0cdacecdebdabeeedddadbdaabbdecaeaabebaaacdcccddebbeeaecdedcacbaabedccdececbdbbcdedbeaccbeaeeebdaaaceb
<2199910 bytes omitted>用户输出
10238
系统信息
Exited with return code 0cddbdacadcdcdeebcbedaeaeaabbbedabecddeaecededdeddddeececadceabcdcbedeccbeeaccbccaeeddaecccbeaedebeba
<2199910 bytes omitted>用户输出
10314
系统信息
Exited with return code 0ecdceedcbcbdbccbccbbeeeceeedcaaeebecceaaecacbacdcdebbceaecddacaadeeedbbeacdbdccccbeaebeaacbdcdecaacd
<2199910 bytes omitted>用户输出
10392
系统信息
Exited with return code 0adeedbeeccaadcebededeadbbbddebdcbcabcbaaddaccdddddeebdeccdedbdbcccebcbdbbcbdcbeeacdbaaebdebadbdaecad
<2199910 bytes omitted>用户输出
10195
系统信息
Exited with return code 0abcacbdccbdaeebbccbbdadacaebceebdacbbcccebdcbacddbabaeccdbcbeeecddeddacabadbbbceeadbaabbcdeedeadcedd
<2199910 bytes omitted>用户输出
10374
系统信息
Exited with return code 0ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
<1502408 bytes omitted>用户输出
999500500
系统信息
Exited with return code 0nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1502408 bytes omitted>用户输出
999500500
系统信息
Exited with return code 0nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1502408 bytes omitted>用户输出
999500500
系统信息
Exited with return code 0iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
<1502408 bytes omitted>用户输出
999500500
系统信息
Exited with return code 0dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
<1502408 bytes omitted>用户输出
999500500
系统信息
Exited with return code 0rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
<1502408 bytes omitted>用户输出
999500500
系统信息
Exited with return code 0kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
<1502408 bytes omitted>用户输出
999500500
系统信息
Exited with return code 0jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj
<1502408 bytes omitted>用户输出
999500500
系统信息
Exited with return code 0pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
<1502408 bytes omitted>用户输出
999500500
系统信息
Exited with return code 0