XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#20587 #1059. 1-07E. JM的模板题 Accepted 100 12595 ms 240024 K C++ / 1.9 K 电类809-廖原 2019-07-26 11:09:22
显示原始代码 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define ULL unsigned long long
#define LL long long
using namespace std;
char ch;
bool fh;
inline void read(int &a) {
    for (fh = 0, ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
        if (ch == '-')
            fh = 1;
    for (a = 0; ch >= '0' && ch <= '9'; ch = getchar()) (a *= 10) += ch - '0';
    if (fh)
        a = -a;
}
char an[1000010];
char bn[1000010];
int lena, lenb;
struct suffix_automaton {
    struct node {
        int ne[26], step;
    } A[1000010 * 2];
    int pre[1000010 * 2];
    int last, cnt;
    int Fin[1000010 * 2];
    int Size[1000010 * 2];
    inline void New(int st) { A[++cnt].step = st; }
    int p, np, q, nq, vi;
    void Extend(int ch) {
        //在这里ch是已经减过'A'的 了
        New(A[last].step + 1);
        p = last;
        np = cnt;
        Size[np] = 1;
        for (; p && !A[p].ne[ch]; p = pre[p]) A[p].ne[ch] = np;
        if (!p)
            pre[np] = 1;
        else {
            q = A[p].ne[ch];
            if (A[q].step != A[p].step + 1) {
                New(A[p].step + 1);
                nq = cnt;
                for (vi = 0; vi < 26; vi++) A[nq].ne[vi] = A[q].ne[vi];
                pre[nq] = pre[q];
                pre[q] = pre[np] = nq;
                for (; A[p].ne[ch] == q; p = pre[p]) A[p].ne[ch] = nq;
            } else
                pre[np] = q;
        }
        last = np;
    }
    void Build() {
        int vj;
        cnt = last = 1;
        for (vj = 1; vj <= lena; vj++) Extend(an[vj] - 'a');
    }
    int Stk[1000010 * 2];
    int stktop;
    void Topu() {
        int vi;
        for (vi = 1; vi <= cnt; vi++) Fin[pre[vi]]++;
        for (vi = 1; vi <= cnt; vi++)
            if (!Fin[vi])
                Stk[++stktop] = vi;
        for (; stktop;) {
            p = Stk[stktop--];
            Size[pre[p]] += Size[p];
            Fin[pre[p]]--;
            if (!Fin[pre[p]] && pre[p])
                Stk[++stktop] = pre[p];
        }
    }
    int Run() {
        int vi;
        for (p = 1, vi = 1; vi <= lenb; p = A[p].ne[bn[vi] - 'a'], vi++)
            if (!A[p].ne[bn[vi] - 'a'])
                return 0;
        return Size[p];
    }
} D;
int num;
LL ans;
int main() {
    scanf("%s", an + 1);
    lena = strlen(an + 1);
    D.Build();
    D.Topu();
    scanf("%d\n", &num);
    for (; num; num--) {
        scanf("%s", bn + 1);
        lenb = strlen(bn + 1);
        ans += D.Run();
    }
    printf("%lld\n", ans);
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：529 ms
内存：239912 KiB

输入文件（1.in） 

ababaaabbbbbbbaabaaaaababababbaaabbaabaabaabaaabbaaababbbabbaababbaabbababbaabbaaabbabbbaaaabaabbbaa
<2000107 bytes omitted>

答案文件（1.out） 

0

用户输出 

0

系统信息 

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

输入文件（2.in） 

bbaaaabaaaabbbbaaabbbbabbaaabaaabbbbbaaabababaabbbaaabbabaaaababaaabababbabaaababbbabbabababaaaababb
<2000107 bytes omitted>

答案文件（2.out） 

0

用户输出 

0

系统信息 

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

输入文件（3.in） 

ababbbaaaababbababaaabbbbabbaabaabbaaababbabbbaaaaaabababbbbabaababaabaaaaaabbbabbabbbbbbbbabbababba
<2000107 bytes omitted>

答案文件（3.out） 

0

用户输出 

0

系统信息 

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

输入文件（4.in） 

bbbbbabbaaabbaaabbabbbabbbabbabaaababbaaabaaabababbaaaabbaaabbbbbbbabbabaabbaabbabababaaaaababbabaaa
<2000107 bytes omitted>

答案文件（4.out） 

0

用户输出 

0

系统信息 

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

输入文件（5.in） 

abaaaaaabbaaaaabaabaabbaaaaabbbbbaababbaaabbaaababbbbaaaaaaaaaaabaababbabbbbaaaaababbbbbbaabbbbabbab
<2000107 bytes omitted>

答案文件（5.out） 

0

用户输出 

0

系统信息 

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

输入文件（6.in） 

babbbbbabbaabbbbabbbababbaaabaabaaabaabbaabbbabbbaaabbbabbbbbbbabbbabaabbbbabbbababaaaabbababaababaa
<2000107 bytes omitted>

答案文件（6.out） 

0

用户输出 

0

系统信息 

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

输入文件（7.in） 

baaaaaaaaabaabbbbbbabababbaabaababbbaababbbbabaabababaabbabaabaabbaaaabaaabbabaabbbbbbabababbbbbbabb
<2000107 bytes omitted>

答案文件（7.out） 

0

用户输出 

0

系统信息 

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

输入文件（8.in） 

baababbbbbbbbaaabbbbbbbbbabbaabbaaaaabababbbbbabbbababaaaaabababbbaababaaaabbbababababbaabbaabbabbab
<2000107 bytes omitted>

答案文件（8.out） 

0

用户输出 

0

系统信息 

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

输入文件（9.in） 

abbbbaabbbbbaabbaaabaaabbbbabbbaaabbbbaaababbbbbbabbaaababaaaaaaabaabbbaaabbbaabbbabbbbabbbbbaababba
<2000107 bytes omitted>

答案文件（9.out） 

0

用户输出 

0

系统信息 

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

输入文件（10.in） 

aaababbbaabbabaaaababbabaaabaabbaabbbbbbbaababbabbbaaababbaabbaaabbabababbaabaaabaaababaaaaaabbabbba
<2000107 bytes omitted>

答案文件（10.out） 

0

用户输出 

0

系统信息 

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

输入文件（11.in） 

cbedbecbbaacaaedadbaaadebacdcdeaebdeaeccaeccedcddadcaeddadcedebeadeeebabeebadaeeccabaececebdabcdcbbe
<2199910 bytes omitted>

答案文件（11.out） 

10266

用户输出 

10266

系统信息 

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

输入文件（12.in） 

caacebdeebebecebcabecedeccdcacaaadeddaddbebeddecaddcebdeaababaebadbbebacdabccdcbdbabdadaeccdecbcccde
<2199910 bytes omitted>

答案文件（12.out） 

10165

用户输出 

10165

系统信息 

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

输入文件（13.in） 

ecacbcbaccbacdedebaebeabaaeabccbedaaceaaeabbbcbbacadbbadeceacbdbdebadcdabcdeeebaaedaaacacebbccecaddb
<2199910 bytes omitted>

答案文件（13.out） 

10003

用户输出 

10003

系统信息 

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

输入文件（14.in） 

dbcdaaebbadbddcebebbbcaabebbadbaeddeadcccddedbabcdbdeebbebbbdaecdadedcaaabedcecbdcdbadbeabeaebcceccb
<2199910 bytes omitted>

答案文件（14.out） 

10297

用户输出 

10297

系统信息 

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

输入文件（15.in） 

eddecaacdbacbedaaaecacecdaedbdcbcaeeddedaacbecbabcbababcbddbabbbaccebcbbecdadadcbeabbdadabbdecdeacee
<2199910 bytes omitted>

答案文件（15.out） 

10355

用户输出 

10355

系统信息 

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

输入文件（16.in） 

cdacecdebdabeeedddadbdaabbdecaeaabebaaacdcccddebbeeaecdedcacbaabedccdececbdbbcdedbeaccbeaeeebdaaaceb
<2199910 bytes omitted>

答案文件（16.out） 

10238

用户输出 

10238

系统信息 

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

输入文件（17.in） 

cddbdacadcdcdeebcbedaeaeaabbbedabecddeaecededdeddddeececadceabcdcbedeccbeeaccbccaeeddaecccbeaedebeba
<2199910 bytes omitted>

答案文件（17.out） 

10314

用户输出 

10314

系统信息 

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

输入文件（18.in） 

ecdceedcbcbdbccbccbbeeeceeedcaaeebecceaaecacbacdcdebbceaecddacaadeeedbbeacdbdccccbeaebeaacbdcdecaacd
<2199910 bytes omitted>

答案文件（18.out） 

10392

用户输出 

10392

系统信息 

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

输入文件（19.in） 

adeedbeeccaadcebededeadbbbddebdcbcabcbaaddaccdddddeebdeccdedbdbcccebcbdbbcbdcbeeacdbaaebdebadbdaecad
<2199910 bytes omitted>

答案文件（19.out） 

10195

用户输出 

10195

系统信息 

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

输入文件（20.in） 

abcacbdccbdaeebbccbbdadacaebceebdacbbcccebdcbacddbabaeccdbcbeeecddeddacabadbbbceeadbaabbcdeedeadcedd
<2199910 bytes omitted>

答案文件（20.out） 

10374

用户输出 

10374

系统信息 

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

输入文件（21.in） 

ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
<1502408 bytes omitted>

答案文件（21.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（22.in） 

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1502408 bytes omitted>

答案文件（22.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（23.in） 

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1502408 bytes omitted>

答案文件（23.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（24.in） 

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
<1502408 bytes omitted>

答案文件（24.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（25.in） 

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
<1502408 bytes omitted>

答案文件（25.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（26.in） 

rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
<1502408 bytes omitted>

答案文件（26.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（27.in） 

kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
<1502408 bytes omitted>

答案文件（27.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（28.in） 

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj
<1502408 bytes omitted>

答案文件（28.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（29.in） 

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
<1502408 bytes omitted>

答案文件（29.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（30.in） 

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll
<1502408 bytes omitted>

答案文件（30.out） 

999500500

用户输出 

999500500

系统信息 

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