CQUPT OJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#25194 #2037. 弦论(another version) Accepted 100 4132 ms 119316 K C++ 11 / 1.5 K 192024212413 2024-12-21 18:17:03
显示原始代码 
#include <bits/stdc++.h>

using namespace std;

namespace SAM {
static const int N = 1e6 + 10, S = 27;
int tot = 1, last = 1, link[N << 1], ch[N << 1][S];
int len[N << 1], endpos[N << 1];
void clear() { tot = last = 1; }
void extend(int w) {
    int p = ++tot, x = last, r, q;
    endpos[p] = 1;
    for (len[last = p] = len[x] + 1; x && !ch[x][w]; x = link[x]) ch[x][w] = p;
    if (!x)
        link[p] = 1;
    else if (len[x] + 1 == len[q = ch[x][w]])
        link[p] = q;
    else {
        link[r = ++tot] = link[q];
        memcpy(ch[r], ch[q], sizeof ch[r]);
        len[r] = len[x] + 1;
        link[p] = link[q] = r;
        for (; x && ch[x][w] == q; x = link[x]) ch[x][w] = r;
    }
}
std::vector<int> p[N << 1];
void dfs(int u) {
    int v;
    for (int i = 0; i < p[u].size(); ++i) {
        v = p[u][i];
        dfs(v);
        endpos[u] += endpos[v];
    }
}
void get_endpos() {
    for (int i = 1; i <= tot; ++i) p[i].clear();
    for (int i = 2; i <= tot; ++i) {
        p[link[i]].push_back(i);
    }
    dfs(1);
    for (int i = 1; i <= tot; ++i) p[i].clear();
}
long long query(string s) {
    int p = 1;
    for (int i = 0; i < s.size(); ++i) {
        int now = s[i] - 'a';
        p = ch[p][now];
        if (!p)
            return 0;
    }
    return endpos[p];
}
}  // namespace SAM

int main() {
    SAM::clear();
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < s.size(); ++j) SAM::extend(s[j] - 'a');
        SAM::extend(26);
    }
    SAM::get_endpos();
    int q;
    cin >> q;
    while (q--) {
        string s;
        cin >> s;
        cout << SAM::query(s) << endl;
    }
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：65 ms
内存：47392 KiB

输入文件（0.in） 

4 10
a
aaa
aa
aaaa
4
a
aa
aaa
aaaa

答案文件（0.out） 

10
6
3
1

用户输出 

10
6
3
1

系统信息 

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

输入文件（1.in） 

3 9
aaa
aba
aab
2
a
aa

答案文件（1.out） 

7
3

用户输出 

7
3

系统信息 

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

输入文件（2.in） 

100 200000
xyhglfbxleieeancsaipttydqghtjmhblotpsuvytxynwaatqiezrilmgxdfqvizbndvsksxzvobqxthgkxvbvgo
<440065 bytes omitted>

答案文件（2.out） 

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
<59918 bytes omitted>

用户输出 

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

<39890 bytes omitted>

系统信息 

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

输入文件（3.in） 

100 200000
hlbcgcmaxdfioijoubnojpmrfohulumwirfarwovepnrwykzrzzfvorynjoxumvhsxpvabbpkryuruclumhmteew
<300119 bytes omitted>

答案文件（3.out） 

14
17
15
15
15
8
10
16
11
10
12
20
16
10
15
19
11
15
15
17
13
7
12
10
11
14
<75736 bytes omitted>

用户输出 

14
17
15
15
15
8
10
16
11
10
12
20
16
10
15
19
11
15
15
17
13
7
12
10
11
14
12
10
18
12
16
12
17
12
18
13
13
17
18
13
23
10
16
1
<55708 bytes omitted>

系统信息 

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

输入文件（5.in） 

100 200000
usnsprodkeljgibmantimnkpzguxfcuobzwxerknjjbccxqlcvunmmymjzlksccstncetmtqecmpxiuxhplazyat
<300119 bytes omitted>

答案文件（5.out） 

11
13
10
15
9
10
8
19
18
15
15
11
11
11
9
11
15
15
16
12
13
7
12
11
14
9
1
<75905 bytes omitted>

用户输出 

11
13
10
15
9
10
8
19
18
15
15
11
11
11
9
11
15
15
16
12
13
7
12
11
14
9
14
12
12
9
14
17
8
14
13
13
5
12
7
10
11
12
7
12
10
15

<55877 bytes omitted>

系统信息 

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

输入文件（6.in） 

100 200000
xobjjfjmjhmgsxasjmbeigsuatjqhaenqcnwjzopjpodnkowiqzlycqbxjqhqrrcqpafuvnyidgbcheftpxttqgo
<298506 bytes omitted>

答案文件（6.out） 

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
<200 bytes omitted>

用户输出 

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

<72 bytes omitted>

系统信息 

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

输入文件（7.in） 

100 200000
ssiwurakptykaljovijyaoopdspzxayggnhfsubqsrpwodufsvwzmpabkgxryesanszczewjystsyftjkspenbre
<292658 bytes omitted>

答案文件（7.out） 

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
<200 bytes omitted>

用户输出 

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

<72 bytes omitted>

系统信息 

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

输入文件（8.in） 

1 200000
higlcljtjjezelczszusltndbahanudplnftpxjkyxcapghfkgsvyrclugymaqrrakvnxscwhvlmqqqdmuojlysapv
<349915 bytes omitted>

答案文件（8.out） 

1

用户输出 

1

系统信息 

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

输入文件（10.in） 

1 200000
aidiygcnhnlugueymginpzbrpkygsddmdamadrrqskbclnetprrwazizyiqpngvzlavrakeiszfflbuieywlnxfcdy
<349935 bytes omitted>

答案文件（10.out） 

0

用户输出 

0

系统信息 

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

输入文件（13.in） 

100 200000
otyctwfxuvhyqqsghwqihvwquekwvsrkbgwayazmcepjgccnugcaexvoavauiviwenyrdrsmrekmsidscuevfogt
<202317 bytes omitted>

答案文件（13.out） 

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
<200 bytes omitted>

用户输出 

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

<72 bytes omitted>

系统信息 

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

输入文件（14.in） 

100 200000
hyzlqvwoyvjgezzmzrzwsbiibebexgaxjlccviwtfcpgzwmbuddlvhruxmndjdgyqxiqgtfopezoxfyndwhbclhx
<600120 bytes omitted>

答案文件（14.out） 

303
290
284
316
314
288
244
307
316
288
275
287
304
297
292
286
304
308
294
289

<549962 bytes omitted>

用户输出 

303
290
284
316
314
288
244
307
316
288
275
287
304
297
292
286
304
308
294
289
273
275
306
292
298
272
331
282
291
287
328
306

<449934 bytes omitted>

系统信息 

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

输入文件（15.in） 

100 200000
hhssofajgkxkqrlkxqrvkkotbaiypfeglpwfltwpryovffwnfdaetqaelpvdwyvuabzjxiudfkvvehoqwhpqbzhn
<800120 bytes omitted>

答案文件（15.out） 

9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
<1199900 bytes omitted>

用户输出 

9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
9659
965
<999872 bytes omitted>

系统信息 

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

输入文件（16.in） 

200000 200000
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
<1199923 bytes omitted>

答案文件（16.out） 

200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
2000
<1599900 bytes omitted>

用户输出 

200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
20
<1399872 bytes omitted>

系统信息 

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

输入文件（17.in） 

1 200000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
<799920 bytes omitted>

答案文件（17.out） 

200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
2000
<1599900 bytes omitted>

用户输出 

200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
20
<1399872 bytes omitted>

系统信息 

Exited with return code 0
CQUPT OJ Powered by SYZOJ.