XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#21981 #1059. 1-07E. JM的模板题 Accepted 100 10520 ms 266160 K C++ 17 / 1.6 K Leohh 2020-02-11 16:26:06
显示原始代码 
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define MAX_T 1000005
#define MAX_A 30
#define int long long

using namespace std;

int n, tot = 1, ans = 0;
int a[MAX_T];
int w[MAX_T];
int f[MAX_T];
int c[MAX_T][MAX_A];
vector<int> e[MAX_T];
queue<int> q;

void insert(const string &s) {
    int x = 1;
    for (int i = 0; i < s.size(); i++) {
        int t = s[i] - 'a';
        if (!c[x][t]) {
            c[x][t] = ++tot;
        }
        x = c[x][t];
    }
    a[x]++;
}

void build() {
    for (int i = 0; i < 26; i++) {
        c[0][i] = 1;
    }
    q.push(1);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < 26; i++) {
            if (c[x][i]) {
                int t = f[x];
                while (!c[t][i]) {
                    t = f[t];
                }
                f[c[x][i]] = c[t][i];
                e[c[t][i]].push_back(c[x][i]);
                q.push(c[x][i]);
            }
        }
    }
}

void match(const string &s) {
    int x = 1;
    for (int i = 0; i < s.size(); i++) {
        int t = s[i] - 'a';
        while (!c[x][t]) {
            x = f[x];
        }
        x = c[x][t];
        w[x]++;
    }
}

void dfs(int x) {
    for (int i = 0; i < e[x].size(); i++) {
        int t = e[x][i];
        dfs(t);
        w[x] += w[t];
    }
    ans += a[x] * w[x];
}

signed main() {
    string s, p;
    cin >> s >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p;
        insert(p);
    }
    build();
    match(s);
    dfs(1);
    cout << ans << endl;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：600 ms
内存：266004 KiB

输入文件（1.in） 

ababaaabbbbbbbaabaaaaababababbaaabbaabaabaabaaabbaaababbbabbaababbaabbababbaabbaaabbabbbaaaabaabbbaa
<2000107 bytes omitted>

答案文件（1.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：366 ms
内存：265924 KiB

输入文件（2.in） 

bbaaaabaaaabbbbaaabbbbabbaaabaaabbbbbaaabababaabbbaaabbabaaaababaaabababbabaaababbbabbabababaaaababb
<2000107 bytes omitted>

答案文件（2.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：375 ms
内存：266016 KiB

输入文件（3.in） 

ababbbaaaababbababaaabbbbabbaabaabbaaababbabbbaaaaaabababbbbabaababaabaaaaaabbbabbabbbbbbbbabbababba
<2000107 bytes omitted>

答案文件（3.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：556 ms
内存：266036 KiB

输入文件（4.in） 

bbbbbabbaaabbaaabbabbbabbbabbabaaababbaaabaaabababbaaaabbaaabbbbbbbabbabaabbaabbabababaaaaababbabaaa
<2000107 bytes omitted>

答案文件（4.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：421 ms
内存：265976 KiB

输入文件（5.in） 

abaaaaaabbaaaaabaabaabbaaaaabbbbbaababbaaabbaaababbbbaaaaaaaaaaabaababbabbbbaaaaababbbbbbaabbbbabbab
<2000107 bytes omitted>

答案文件（5.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：390 ms
内存：265956 KiB

输入文件（6.in） 

babbbbbabbaabbbbabbbababbaaabaabaaabaabbaabbbabbbaaabbbabbbbbbbabbbabaabbbbabbbababaaaabbababaababaa
<2000107 bytes omitted>

答案文件（6.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：348 ms
内存：266160 KiB

输入文件（7.in） 

baaaaaaaaabaabbbbbbabababbaabaababbbaababbbbabaabababaabbabaabaabbaaaabaaabbabaabbbbbbabababbbbbbabb
<2000107 bytes omitted>

答案文件（7.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：352 ms
内存：265864 KiB

输入文件（8.in） 

baababbbbbbbbaaabbbbbbbbbabbaabbaaaaabababbbbbabbbababaaaaabababbbaababaaaabbbababababbaabbaabbabbab
<2000107 bytes omitted>

答案文件（8.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：430 ms
内存：265860 KiB

输入文件（9.in） 

abbbbaabbbbbaabbaaabaaabbbbabbbaaabbbbaaababbbbbbabbaaababaaaaaaabaabbbaaabbbaabbbabbbbabbbbbaababba
<2000107 bytes omitted>

答案文件（9.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：359 ms
内存：266076 KiB

输入文件（10.in） 

aaababbbaabbabaaaababbabaaabaabbaabbbbbbbaababbabbbaaababbaabbaaabbabababbaabaaabaaababaaaaaabbabbba
<2000107 bytes omitted>

答案文件（10.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：578 ms
内存：112324 KiB

输入文件（11.in） 

cbedbecbbaacaaedadbaaadebacdcdeaebdeaeccaeccedcddadcaeddadcedebeadeeebabeebadaeeccabaececebdabcdcbbe
<2199910 bytes omitted>

答案文件（11.out） 

10266

用户输出 

10266

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：625 ms
内存：112280 KiB

输入文件（12.in） 

caacebdeebebecebcabecedeccdcacaaadeddaddbebeddecaddcebdeaababaebadbbebacdabccdcbdbabdadaeccdecbcccde
<2199910 bytes omitted>

答案文件（12.out） 

10165

用户输出 

10165

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：548 ms
内存：112304 KiB

输入文件（13.in） 

ecacbcbaccbacdedebaebeabaaeabccbedaaceaaeabbbcbbacadbbadeceacbdbdebadcdabcdeeebaaedaaacacebbccecaddb
<2199910 bytes omitted>

答案文件（13.out） 

10003

用户输出 

10003

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：652 ms
内存：112244 KiB

输入文件（14.in） 

dbcdaaebbadbddcebebbbcaabebbadbaeddeadcccddedbabcdbdeebbebbbdaecdadedcaaabedcecbdcdbadbeabeaebcceccb
<2199910 bytes omitted>

答案文件（14.out） 

10297

用户输出 

10297

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：620 ms
内存：112284 KiB

输入文件（15.in） 

eddecaacdbacbedaaaecacecdaedbdcbcaeeddedaacbecbabcbababcbddbabbbaccebcbbecdadadcbeabbdadabbdecdeacee
<2199910 bytes omitted>

答案文件（15.out） 

10355

用户输出 

10355

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：593 ms
内存：112316 KiB

输入文件（16.in） 

cdacecdebdabeeedddadbdaabbdecaeaabebaaacdcccddebbeeaecdedcacbaabedccdececbdbbcdedbeaccbeaeeebdaaaceb
<2199910 bytes omitted>

答案文件（16.out） 

10238

用户输出 

10238

系统信息 

Exited with return code 0
测试点 #17
Accepted
得分：100
用时：596 ms
内存：112296 KiB

输入文件（17.in） 

cddbdacadcdcdeebcbedaeaeaabbbedabecddeaecededdeddddeececadceabcdcbedeccbeeaccbccaeeddaecccbeaedebeba
<2199910 bytes omitted>

答案文件（17.out） 

10314

用户输出 

10314

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：572 ms
内存：112336 KiB

输入文件（18.in） 

ecdceedcbcbdbccbccbbeeeceeedcaaeebecceaaecacbacdcdebbceaecddacaadeeedbbeacdbdccccbeaebeaacbdcdecaacd
<2199910 bytes omitted>

答案文件（18.out） 

10392

用户输出 

10392

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：661 ms
内存：112276 KiB

输入文件（19.in） 

adeedbeeccaadcebededeadbbbddebdcbcabcbaaddaccdddddeebdeccdedbdbcccebcbdbbcbdcbeeacdbaaebdebadbdaecad
<2199910 bytes omitted>

答案文件（19.out） 

10195

用户输出 

10195

系统信息 

Exited with return code 0
测试点 #20
Accepted
得分：100
用时：507 ms
内存：112252 KiB

输入文件（20.in） 

abcacbdccbdaeebbccbbdadacaebceebdacbbcccebdcbacddbabaeccdbcbeeecddeddacabadbbbceeadbaabbcdeedeadcedd
<2199910 bytes omitted>

答案文件（20.out） 

10374

用户输出 

10374

系统信息 

Exited with return code 0
测试点 #21
Accepted
得分：100
用时：34 ms
内存：14120 KiB

输入文件（21.in） 

ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
<1502408 bytes omitted>

答案文件（21.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #22
Accepted
得分：100
用时：36 ms
内存：14060 KiB

输入文件（22.in） 

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1502408 bytes omitted>

答案文件（22.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #23
Accepted
得分：100
用时：38 ms
内存：14056 KiB

输入文件（23.in） 

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1502408 bytes omitted>

答案文件（23.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #24
Accepted
得分：100
用时：36 ms
内存：14040 KiB

输入文件（24.in） 

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
<1502408 bytes omitted>

答案文件（24.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #25
Accepted
得分：100
用时：35 ms
内存：14092 KiB

输入文件（25.in） 

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
<1502408 bytes omitted>

答案文件（25.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #26
Accepted
得分：100
用时：51 ms
内存：14132 KiB

输入文件（26.in） 

rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
<1502408 bytes omitted>

答案文件（26.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #27
Accepted
得分：100
用时：36 ms
内存：14052 KiB

输入文件（27.in） 

kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
<1502408 bytes omitted>

答案文件（27.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #28
Accepted
得分：100
用时：35 ms
内存：14100 KiB

输入文件（28.in） 

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj
<1502408 bytes omitted>

答案文件（28.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #29
Accepted
得分：100
用时：34 ms
内存：14032 KiB

输入文件（29.in） 

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
<1502408 bytes omitted>

答案文件（29.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
测试点 #30
Accepted
得分：100
用时：36 ms
内存：14144 KiB

输入文件（30.in） 

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll
<1502408 bytes omitted>

答案文件（30.out） 

999500500

用户输出 

999500500

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ. | 鲁ICP备2020034929号