编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#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;
}
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:182 ms
内存:221896 KiB

输入文件(1.in

ababaaabbbbbbbaabaaaaababababbaaabbaabaabaabaaabbaaababbbabbaababbaabbababbaabbaaabbabbbaaaabaabbbaa
<2000107 bytes omitted>

答案文件(1.out

0

用户输出

0

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:178 ms
内存:221888 KiB

输入文件(2.in

bbaaaabaaaabbbbaaabbbbabbaaabaaabbbbbaaabababaabbbaaabbabaaaababaaabababbabaaababbbabbabababaaaababb
<2000107 bytes omitted>

答案文件(2.out

0

用户输出

0

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:179 ms
内存:221940 KiB

输入文件(3.in

ababbbaaaababbababaaabbbbabbaabaabbaaababbabbbaaaaaabababbbbabaababaabaaaaaabbbabbabbbbbbbbabbababba
<2000107 bytes omitted>

答案文件(3.out

0

用户输出

0

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:179 ms
内存:221928 KiB

输入文件(4.in

bbbbbabbaaabbaaabbabbbabbbabbabaaababbaaabaaabababbaaaabbaaabbbbbbbabbabaabbaabbabababaaaaababbabaaa
<2000107 bytes omitted>

答案文件(4.out

0

用户输出

0

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:171 ms
内存:221948 KiB

输入文件(5.in

abaaaaaabbaaaaabaabaabbaaaaabbbbbaababbaaabbaaababbbbaaaaaaaaaaabaababbabbbbaaaaababbbbbbaabbbbabbab
<2000107 bytes omitted>

答案文件(5.out

0

用户输出

0

系统信息

Exited with return code 0
测试点 #6
Accepted
得分:100
用时:182 ms
内存:221940 KiB

输入文件(6.in

babbbbbabbaabbbbabbbababbaaabaabaaabaabbaabbbabbbaaabbbabbbbbbbabbbabaabbbbabbbababaaaabbababaababaa
<2000107 bytes omitted>

答案文件(6.out

0

用户输出

0

系统信息

Exited with return code 0
测试点 #7
Accepted
得分:100
用时:167 ms
内存:221956 KiB

输入文件(7.in

baaaaaaaaabaabbbbbbabababbaabaababbbaababbbbabaabababaabbabaabaabbaaaabaaabbabaabbbbbbabababbbbbbabb
<2000107 bytes omitted>

答案文件(7.out

0

用户输出

0

系统信息

Exited with return code 0
测试点 #8
Accepted
得分:100
用时:210 ms
内存:221952 KiB

输入文件(8.in

baababbbbbbbbaaabbbbbbbbbabbaabbaaaaabababbbbbabbbababaaaaabababbbaababaaaabbbababababbaabbaabbabbab
<2000107 bytes omitted>

答案文件(8.out

0

用户输出

0

系统信息

Exited with return code 0
测试点 #9
Accepted
得分:100
用时:186 ms
内存:221980 KiB

输入文件(9.in

abbbbaabbbbbaabbaaabaaabbbbabbbaaabbbbaaababbbbbbabbaaababaaaaaaabaabbbaaabbbaabbbabbbbabbbbbaababba
<2000107 bytes omitted>

答案文件(9.out

0

用户输出

0

系统信息

Exited with return code 0
测试点 #10
Accepted
得分:100
用时:193 ms
内存:221884 KiB

输入文件(10.in

aaababbbaabbabaaaababbabaaabaabbaabbbbbbbaababbabbbaaababbaabbaaabbabababbaabaaabaaababaaaaaabbabbba
<2000107 bytes omitted>

答案文件(10.out

0

用户输出

0

系统信息

Exited with return code 0
测试点 #11
Accepted
得分:100
用时:312 ms
内存:89816 KiB

输入文件(11.in

cbedbecbbaacaaedadbaaadebacdcdeaebdeaeccaeccedcddadcaeddadcedebeadeeebabeebadaeeccabaececebdabcdcbbe
<2199910 bytes omitted>

答案文件(11.out

10266

用户输出

10266

系统信息

Exited with return code 0
测试点 #12
Accepted
得分:100
用时:308 ms
内存:89672 KiB

输入文件(12.in

caacebdeebebecebcabecedeccdcacaaadeddaddbebeddecaddcebdeaababaebadbbebacdabccdcbdbabdadaeccdecbcccde
<2199910 bytes omitted>

答案文件(12.out

10165

用户输出

10165

系统信息

Exited with return code 0
测试点 #13
Accepted
得分:100
用时:277 ms
内存:89724 KiB

输入文件(13.in

ecacbcbaccbacdedebaebeabaaeabccbedaaceaaeabbbcbbacadbbadeceacbdbdebadcdabcdeeebaaedaaacacebbccecaddb
<2199910 bytes omitted>

答案文件(13.out

10003

用户输出

10003

系统信息

Exited with return code 0
测试点 #14
Accepted
得分:100
用时:286 ms
内存:89728 KiB

输入文件(14.in

dbcdaaebbadbddcebebbbcaabebbadbaeddeadcccddedbabcdbdeebbebbbdaecdadedcaaabedcecbdcdbadbeabeaebcceccb
<2199910 bytes omitted>

答案文件(14.out

10297

用户输出

10297

系统信息

Exited with return code 0
测试点 #15
Accepted
得分:100
用时:301 ms
内存:89728 KiB

输入文件(15.in

eddecaacdbacbedaaaecacecdaedbdcbcaeeddedaacbecbabcbababcbddbabbbaccebcbbecdadadcbeabbdadabbdecdeacee
<2199910 bytes omitted>

答案文件(15.out

10355

用户输出

10355

系统信息

Exited with return code 0
测试点 #16
Accepted
得分:100
用时:298 ms
内存:89696 KiB

输入文件(16.in

cdacecdebdabeeedddadbdaabbdecaeaabebaaacdcccddebbeeaecdedcacbaabedccdececbdbbcdedbeaccbeaeeebdaaaceb
<2199910 bytes omitted>

答案文件(16.out

10238

用户输出

10238

系统信息

Exited with return code 0
测试点 #17
Accepted
得分:100
用时:308 ms
内存:89664 KiB

输入文件(17.in

cddbdacadcdcdeebcbedaeaeaabbbedabecddeaecededdeddddeececadceabcdcbedeccbeeaccbccaeeddaecccbeaedebeba
<2199910 bytes omitted>

答案文件(17.out

10314

用户输出

10314

系统信息

Exited with return code 0
测试点 #18
Accepted
得分:100
用时:290 ms
内存:89792 KiB

输入文件(18.in

ecdceedcbcbdbccbccbbeeeceeedcaaeebecceaaecacbacdcdebbceaecddacaadeeedbbeacdbdccccbeaebeaacbdcdecaacd
<2199910 bytes omitted>

答案文件(18.out

10392

用户输出

10392

系统信息

Exited with return code 0
测试点 #19
Accepted
得分:100
用时:290 ms
内存:89720 KiB

输入文件(19.in

adeedbeeccaadcebededeadbbbddebdcbcabcbaaddaccdddddeebdeccdedbdbcccebcbdbbcbdcbeeacdbaaebdebadbdaecad
<2199910 bytes omitted>

答案文件(19.out

10195

用户输出

10195

系统信息

Exited with return code 0
测试点 #20
Accepted
得分:100
用时:298 ms
内存:89728 KiB

输入文件(20.in

abcacbdccbdaeebbccbbdadacaebceebdacbbcccebdcbacddbabaeccdbcbeeecddeddacabadbbbceeadbaabbcdeedeadcedd
<2199910 bytes omitted>

答案文件(20.out

10374

用户输出

10374

系统信息

Exited with return code 0
测试点 #21
Accepted
得分:100
用时:12 ms
内存:1512 KiB

输入文件(21.in

ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
<1502408 bytes omitted>

答案文件(21.out

999500500

用户输出

999500500

系统信息

Exited with return code 0
测试点 #22
Accepted
得分:100
用时:12 ms
内存:1528 KiB

输入文件(22.in

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1502408 bytes omitted>

答案文件(22.out

999500500

用户输出

999500500

系统信息

Exited with return code 0
测试点 #23
Accepted
得分:100
用时:12 ms
内存:1556 KiB

输入文件(23.in

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1502408 bytes omitted>

答案文件(23.out

999500500

用户输出

999500500

系统信息

Exited with return code 0
测试点 #24
Accepted
得分:100
用时:14 ms
内存:1536 KiB

输入文件(24.in

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
<1502408 bytes omitted>

答案文件(24.out

999500500

用户输出

999500500

系统信息

Exited with return code 0
测试点 #25
Accepted
得分:100
用时:12 ms
内存:1532 KiB

输入文件(25.in

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
<1502408 bytes omitted>

答案文件(25.out

999500500

用户输出

999500500

系统信息

Exited with return code 0
测试点 #26
Accepted
得分:100
用时:13 ms
内存:1628 KiB

输入文件(26.in

rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
<1502408 bytes omitted>

答案文件(26.out

999500500

用户输出

999500500

系统信息

Exited with return code 0
测试点 #27
Accepted
得分:100
用时:13 ms
内存:1528 KiB

输入文件(27.in

kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
<1502408 bytes omitted>

答案文件(27.out

999500500

用户输出

999500500

系统信息

Exited with return code 0
测试点 #28
Accepted
得分:100
用时:14 ms
内存:1520 KiB

输入文件(28.in

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj
<1502408 bytes omitted>

答案文件(28.out

999500500

用户输出

999500500

系统信息

Exited with return code 0
测试点 #29
Accepted
得分:100
用时:12 ms
内存:1600 KiB

输入文件(29.in

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
<1502408 bytes omitted>

答案文件(29.out

999500500

用户输出

999500500

系统信息

Exited with return code 0
测试点 #30
Accepted
得分:100
用时:12 ms
内存:1612 KiB

输入文件(30.in

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll
<1502408 bytes omitted>

答案文件(30.out

999500500

用户输出

999500500

系统信息

Exited with return code 0