ababaaabbbbbbbaabaaaaababababbaaabbaabaabaabaaabbaaababbbabbaababbaabbababbaabbaaabbabbbaaaabaabbbaa
<2000107 bytes omitted>
用户输出
0
系统信息
Exited with return code 0
编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
---|---|---|---|---|---|---|---|---|
#111692 | #1059. 1-07E. JM的模板题 | Accepted | 100 | 4921 ms | 221980 K | C++ 17 / 1.3 K | Flyic | 2024-07-11 12:41:52 |
#include <bits/stdc++.h>
using namespace std;
#define int long long
int nxt[2000010][26], cnt = 1, exist[2000010], ans[2000010], id[2000010], fail[2000010], deg[2000010];
int vis[2000010];
void insert(char *s, int len, int num) {
int p = 1;
for (int i = 0; i < len; ++i) {
int c = s[i] - 'a';
if (!nxt[p][c])
nxt[p][c] = ++cnt;
p = nxt[p][c];
}
if (!exist[p])
exist[p] = num, id[num] = num;
else
id[num] = exist[p];
}
void getfail() {
queue<int> q;
for (int i = 0; i < 26; ++i) nxt[0][i] = 1;
q.push(1);
while (!q.empty()) {
int u = q.front();
q.pop();
int Fail = fail[u];
for (int i = 0; i < 26; ++i) {
int v = nxt[u][i];
if (!v) {
nxt[u][i] = nxt[Fail][i];
continue;
}
fail[v] = nxt[Fail][i];
++deg[fail[v]];
q.push(v);
}
}
}
void toposort() {
queue<int> q;
for (int i = 1; i <= cnt; ++i)
if (deg[i] == 0)
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
vis[exist[u]] = ans[u];
int v = fail[u];
--deg[v];
if (!deg[v])
q.push(v);
ans[v] += ans[u];
}
}
void query(char *s, int len) {
int p = 1;
for (int i = 0; i < len; ++i) p = nxt[p][s[i] - 'a'], ++ans[p];
}
char t[2000010], s[2000010];
signed main() {
scanf("%s", s);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
scanf("%s", t);
insert(t, strlen(t), i);
}
getfail();
query(s, strlen(s));
toposort();
int ans = 0;
for (int i = 1; i <= n; ++i) ans += vis[id[i]];
cout << ans;
return 0;
}
ababaaabbbbbbbaabaaaaababababbaaabbaabaabaabaaabbaaababbbabbaababbaabbababbaabbaaabbabbbaaaabaabbbaa
<2000107 bytes omitted>
用户输出
0
系统信息
Exited with return code 0
bbaaaabaaaabbbbaaabbbbabbaaabaaabbbbbaaabababaabbbaaabbabaaaababaaabababbabaaababbbabbabababaaaababb
<2000107 bytes omitted>
用户输出
0
系统信息
Exited with return code 0
ababbbaaaababbababaaabbbbabbaabaabbaaababbabbbaaaaaabababbbbabaababaabaaaaaabbbabbabbbbbbbbabbababba
<2000107 bytes omitted>
用户输出
0
系统信息
Exited with return code 0
bbbbbabbaaabbaaabbabbbabbbabbabaaababbaaabaaabababbaaaabbaaabbbbbbbabbabaabbaabbabababaaaaababbabaaa
<2000107 bytes omitted>
用户输出
0
系统信息
Exited with return code 0
abaaaaaabbaaaaabaabaabbaaaaabbbbbaababbaaabbaaababbbbaaaaaaaaaaabaababbabbbbaaaaababbbbbbaabbbbabbab
<2000107 bytes omitted>
用户输出
0
系统信息
Exited with return code 0
babbbbbabbaabbbbabbbababbaaabaabaaabaabbaabbbabbbaaabbbabbbbbbbabbbabaabbbbabbbababaaaabbababaababaa
<2000107 bytes omitted>
用户输出
0
系统信息
Exited with return code 0
baaaaaaaaabaabbbbbbabababbaabaababbbaababbbbabaabababaabbabaabaabbaaaabaaabbabaabbbbbbabababbbbbbabb
<2000107 bytes omitted>
用户输出
0
系统信息
Exited with return code 0
baababbbbbbbbaaabbbbbbbbbabbaabbaaaaabababbbbbabbbababaaaaabababbbaababaaaabbbababababbaabbaabbabbab
<2000107 bytes omitted>
用户输出
0
系统信息
Exited with return code 0
abbbbaabbbbbaabbaaabaaabbbbabbbaaabbbbaaababbbbbbabbaaababaaaaaaabaabbbaaabbbaabbbabbbbabbbbbaababba
<2000107 bytes omitted>
用户输出
0
系统信息
Exited with return code 0
aaababbbaabbabaaaababbabaaabaabbaabbbbbbbaababbabbbaaababbaabbaaabbabababbaabaaabaaababaaaaaabbabbba
<2000107 bytes omitted>
用户输出
0
系统信息
Exited with return code 0
cbedbecbbaacaaedadbaaadebacdcdeaebdeaeccaeccedcddadcaeddadcedebeadeeebabeebadaeeccabaececebdabcdcbbe
<2199910 bytes omitted>
用户输出
10266
系统信息
Exited with return code 0
caacebdeebebecebcabecedeccdcacaaadeddaddbebeddecaddcebdeaababaebadbbebacdabccdcbdbabdadaeccdecbcccde
<2199910 bytes omitted>
用户输出
10165
系统信息
Exited with return code 0
ecacbcbaccbacdedebaebeabaaeabccbedaaceaaeabbbcbbacadbbadeceacbdbdebadcdabcdeeebaaedaaacacebbccecaddb
<2199910 bytes omitted>
用户输出
10003
系统信息
Exited with return code 0
dbcdaaebbadbddcebebbbcaabebbadbaeddeadcccddedbabcdbdeebbebbbdaecdadedcaaabedcecbdcdbadbeabeaebcceccb
<2199910 bytes omitted>
用户输出
10297
系统信息
Exited with return code 0
eddecaacdbacbedaaaecacecdaedbdcbcaeeddedaacbecbabcbababcbddbabbbaccebcbbecdadadcbeabbdadabbdecdeacee
<2199910 bytes omitted>
用户输出
10355
系统信息
Exited with return code 0
cdacecdebdabeeedddadbdaabbdecaeaabebaaacdcccddebbeeaecdedcacbaabedccdececbdbbcdedbeaccbeaeeebdaaaceb
<2199910 bytes omitted>
用户输出
10238
系统信息
Exited with return code 0
cddbdacadcdcdeebcbedaeaeaabbbedabecddeaecededdeddddeececadceabcdcbedeccbeeaccbccaeeddaecccbeaedebeba
<2199910 bytes omitted>
用户输出
10314
系统信息
Exited with return code 0
ecdceedcbcbdbccbccbbeeeceeedcaaeebecceaaecacbacdcdebbceaecddacaadeeedbbeacdbdccccbeaebeaacbdcdecaacd
<2199910 bytes omitted>
用户输出
10392
系统信息
Exited with return code 0
adeedbeeccaadcebededeadbbbddebdcbcabcbaaddaccdddddeebdeccdedbdbcccebcbdbbcbdcbeeacdbaaebdebadbdaecad
<2199910 bytes omitted>
用户输出
10195
系统信息
Exited with return code 0
abcacbdccbdaeebbccbbdadacaebceebdacbbcccebdcbacddbabaeccdbcbeeecddeddacabadbbbceeadbaabbcdeedeadcedd
<2199910 bytes omitted>
用户输出
10374
系统信息
Exited with return code 0
ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
<1502408 bytes omitted>
用户输出
999500500
系统信息
Exited with return code 0
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1502408 bytes omitted>
用户输出
999500500
系统信息
Exited with return code 0
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1502408 bytes omitted>
用户输出
999500500
系统信息
Exited with return code 0
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
<1502408 bytes omitted>
用户输出
999500500
系统信息
Exited with return code 0
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
<1502408 bytes omitted>
用户输出
999500500
系统信息
Exited with return code 0
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
<1502408 bytes omitted>
用户输出
999500500
系统信息
Exited with return code 0
kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
<1502408 bytes omitted>
用户输出
999500500
系统信息
Exited with return code 0
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj
<1502408 bytes omitted>
用户输出
999500500
系统信息
Exited with return code 0
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
<1502408 bytes omitted>
用户输出
999500500
系统信息
Exited with return code 0