XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#20466 #1059. 1-07E. JM的模板题 Accepted 100 6103 ms 124660 K C++ / 2.1 K q3540555 2019-07-22 15:25:47
显示原始代码 
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define spause() system("pause")

using namespace std;
typedef long long llong;
typedef unsigned long long ullong;
typedef pair<int, int> prdd;
typedef map<int, int> mpdd;

const int dinf = 0x7fffffff;
const llong llinf = 0x7fffffffffffffff;
const int p = 998244353;
llong starttime;

struct sgtrie {
    int num = 0, fail = 0, match = 0, sve = 0;
    int nexts[26] = { 0 };
};

vector<sgtrie> trie;
string txt, mode;
int nom, tid = 0;

void bldac() {
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (int i = 0; i < 26; i++) {
            int cur = trie.at(t).nexts[i];
            if (cur) {
                q.push(cur);
                if (t)
                    trie.at(cur).fail = trie.at(trie.at(t).fail).nexts[i];
                else
                    trie.at(cur).fail = 0;
                trie.at(cur).match = trie.at(cur).num ? cur : trie.at(trie.at(cur).fail).match;
                trie.at(cur).sve = trie.at(cur).num + trie.at(trie.at(cur).fail).sve;
            } else
                trie.at(t).nexts[i] = trie.at(trie.at(t).fail).nexts[i];
        }
    }
}

int search(string s) {
    int ret = 0, cur = 0;
    for (int i = 0; i < s.length(); i++) {
        cur = trie.at(cur).nexts[s.at(i) - 'a'];
        ret += trie.at(cur).sve;
    }
    return ret;
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cin >> txt >> nom;
    // cout << txt.length() << endl;
    starttime = clock();
    trie.push_back(sgtrie());
    for (int i = 0; i < nom; i++) {
        cin >> mode;
        int nwid = 0;
        for (int j = 0; j < mode.length(); j++)
            if (trie.at(nwid).nexts[mode.at(j) - 'a'])
                nwid = trie.at(nwid).nexts[mode.at(j) - 'a'];
            else {
                trie.push_back(sgtrie());
                trie.at(nwid).nexts[mode.at(j) - 'a'] = ++tid;
                nwid = tid;
            }
        trie.at(nwid).num++;
    }

    bldac();
    int ans = search(txt);
    // cout << "\nDebug Info: " << clock() - starttime << " ms passed!\n";
    printf("%d", ans);

    spause();
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：311 ms
内存：124660 KiB

输入文件（1.in） 

ababaaabbbbbbbaabaaaaababababbaaabbaabaabaabaaabbaaababbbabbaababbaabbababbaabbaaabbabbbaaaabaabbbaa
<2000107 bytes omitted>

答案文件（1.out） 

0

用户输出 

0

系统信息 

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

输入文件（2.in） 

bbaaaabaaaabbbbaaabbbbabbaaabaaabbbbbaaabababaabbbaaabbabaaaababaaabababbabaaababbbabbabababaaaababb
<2000107 bytes omitted>

答案文件（2.out） 

0

用户输出 

0

系统信息 

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

输入文件（3.in） 

ababbbaaaababbababaaabbbbabbaabaabbaaababbabbbaaaaaabababbbbabaababaabaaaaaabbbabbabbbbbbbbabbababba
<2000107 bytes omitted>

答案文件（3.out） 

0

用户输出 

0

系统信息 

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

输入文件（4.in） 

bbbbbabbaaabbaaabbabbbabbbabbabaaababbaaabaaabababbaaaabbaaabbbbbbbabbabaabbaabbabababaaaaababbabaaa
<2000107 bytes omitted>

答案文件（4.out） 

0

用户输出 

0

系统信息 

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

输入文件（5.in） 

abaaaaaabbaaaaabaabaabbaaaaabbbbbaababbaaabbaaababbbbaaaaaaaaaaabaababbabbbbaaaaababbbbbbaabbbbabbab
<2000107 bytes omitted>

答案文件（5.out） 

0

用户输出 

0

系统信息 

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

输入文件（6.in） 

babbbbbabbaabbbbabbbababbaaabaabaaabaabbaabbbabbbaaabbbabbbbbbbabbbabaabbbbabbbababaaaabbababaababaa
<2000107 bytes omitted>

答案文件（6.out） 

0

用户输出 

0

系统信息 

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

输入文件（7.in） 

baaaaaaaaabaabbbbbbabababbaabaababbbaababbbbabaabababaabbabaabaabbaaaabaaabbabaabbbbbbabababbbbbbabb
<2000107 bytes omitted>

答案文件（7.out） 

0

用户输出 

0

系统信息 

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

输入文件（8.in） 

baababbbbbbbbaaabbbbbbbbbabbaabbaaaaabababbbbbabbbababaaaaabababbbaababaaaabbbababababbaabbaabbabbab
<2000107 bytes omitted>

答案文件（8.out） 

0

用户输出 

0

系统信息 

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

输入文件（9.in） 

abbbbaabbbbbaabbaaabaaabbbbabbbaaabbbbaaababbbbbbabbaaababaaaaaaabaabbbaaabbbaabbbabbbbabbbbbaababba
<2000107 bytes omitted>

答案文件（9.out） 

0

用户输出 

0

系统信息 

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

输入文件（10.in） 

aaababbbaabbabaaaababbabaaabaabbaabbbbbbbaababbabbbaaababbaabbaaabbabababbaabaaabaaababaaaaaabbabbba
<2000107 bytes omitted>

答案文件（10.out） 

0

用户输出 

0

系统信息 

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

输入文件（11.in） 

cbedbecbbaacaaedadbaaadebacdcdeaebdeaeccaeccedcddadcaeddadcedebeadeeebabeebadaeeccabaececebdabcdcbbe
<2199910 bytes omitted>

答案文件（11.out） 

10266

用户输出 

10266

系统信息 

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

输入文件（12.in） 

caacebdeebebecebcabecedeccdcacaaadeddaddbebeddecaddcebdeaababaebadbbebacdabccdcbdbabdadaeccdecbcccde
<2199910 bytes omitted>

答案文件（12.out） 

10165

用户输出 

10165

系统信息 

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

输入文件（13.in） 

ecacbcbaccbacdedebaebeabaaeabccbedaaceaaeabbbcbbacadbbadeceacbdbdebadcdabcdeeebaaedaaacacebbccecaddb
<2199910 bytes omitted>

答案文件（13.out） 

10003

用户输出 

10003

系统信息 

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

输入文件（14.in） 

dbcdaaebbadbddcebebbbcaabebbadbaeddeadcccddedbabcdbdeebbebbbdaecdadedcaaabedcecbdcdbadbeabeaebcceccb
<2199910 bytes omitted>

答案文件（14.out） 

10297

用户输出 

10297

系统信息 

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

输入文件（15.in） 

eddecaacdbacbedaaaecacecdaedbdcbcaeeddedaacbecbabcbababcbddbabbbaccebcbbecdadadcbeabbdadabbdecdeacee
<2199910 bytes omitted>

答案文件（15.out） 

10355

用户输出 

10355

系统信息 

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

输入文件（16.in） 

cdacecdebdabeeedddadbdaabbdecaeaabebaaacdcccddebbeeaecdedcacbaabedccdececbdbbcdedbeaccbeaeeebdaaaceb
<2199910 bytes omitted>

答案文件（16.out） 

10238

用户输出 

10238

系统信息 

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

输入文件（17.in） 

cddbdacadcdcdeebcbedaeaeaabbbedabecddeaecededdeddddeececadceabcdcbedeccbeeaccbccaeeddaecccbeaedebeba
<2199910 bytes omitted>

答案文件（17.out） 

10314

用户输出 

10314

系统信息 

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

输入文件（18.in） 

ecdceedcbcbdbccbccbbeeeceeedcaaeebecceaaecacbacdcdebbceaecddacaadeeedbbeacdbdccccbeaebeaacbdcdecaacd
<2199910 bytes omitted>

答案文件（18.out） 

10392

用户输出 

10392

系统信息 

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

输入文件（19.in） 

adeedbeeccaadcebededeadbbbddebdcbcabcbaaddaccdddddeebdeccdedbdbcccebcbdbbcbdcbeeacdbaaebdebadbdaecad
<2199910 bytes omitted>

答案文件（19.out） 

10195

用户输出 

10195

系统信息 

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

输入文件（20.in） 

abcacbdccbdaeebbccbbdadacaebceebdacbbcccebdcbacddbabaeccdbcbeeecddeddacabadbbbceeadbaabbcdeedeadcedd
<2199910 bytes omitted>

答案文件（20.out） 

10374

用户输出 

10374

系统信息 

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

输入文件（21.in） 

ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
<1502408 bytes omitted>

答案文件（21.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（22.in） 

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1502408 bytes omitted>

答案文件（22.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（23.in） 

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1502408 bytes omitted>

答案文件（23.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（24.in） 

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
<1502408 bytes omitted>

答案文件（24.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（25.in） 

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
<1502408 bytes omitted>

答案文件（25.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（26.in） 

rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
<1502408 bytes omitted>

答案文件（26.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（27.in） 

kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
<1502408 bytes omitted>

答案文件（27.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（28.in） 

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj
<1502408 bytes omitted>

答案文件（28.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（29.in） 

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
<1502408 bytes omitted>

答案文件（29.out） 

999500500

用户输出 

999500500

系统信息 

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

输入文件（30.in） 

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll
<1502408 bytes omitted>

答案文件（30.out） 

999500500

用户输出 

999500500

系统信息 

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