CQUPT OJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#24964 #2037. 弦论(another version) Time Limit Exceeded 50 10874 ms 8684 K C++ / 1.1 K 192023211761 2024-12-21 17:13:50
显示原始代码 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, q;
vector<string> strs;
int find(string pattern, string text) {
    int n = pattern.size();
    int m = text.size();
    if (n > m)
        return 0;
    int count = 0;
    vector<int> next(n + 1, 0);
    for (int i = 1; i < n; i++) {
        int j = i;
        while (j > 0) {
            j = next[j];
            if (pattern[j] == pattern[i]) {
                next[i + 1] = j + 1;
                break;
            }
        }
    }
    vector<int> positions;
    for (int i = 0, j = 0; i < m; i++) {
        if (j < n && text[i] == pattern[j]) {
            j++;
        } else {
            while (j > 0) {
                j = next[j];
                if (text[i] == pattern[j]) {
                    j++;
                    break;
                }
            }
        }
        if (j == n) {
            positions.push_back(i - n + 1);
            count++;
        }
    }
    return count;
}
int main() {
    cin >> n >> m;
    while (n--) {
        string str;
        cin >> str;
        strs.push_back(str);
    }
    cin >> q;
    while (q--) {
        string str1;
        cin >> str1;
        int sum = 0;
        for (int i = 0; i < strs.size(); i++) {
            sum += find(str1, strs[i]);
        }
        cout << sum << endl;
    }
    return 0;
}
子任务 #1
Time Limit Exceeded
得分：50
测试点 #1
Accepted
得分：100
用时：4 ms
内存：324 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
用时：4 ms
内存：344 KiB

输入文件（1.in） 

3 9
aaa
aba
aab
2
a
aa

答案文件（1.out） 

7
3

用户输出 

7
3

系统信息 

Exited with return code 0
测试点 #3
Time Limit Exceeded
得分：0
用时：1505 ms
内存：680 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

<7558 bytes omitted>
测试点 #4
Time Limit Exceeded
得分：0
用时：1549 ms
内存：668 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
<11347 bytes omitted>
测试点 #5
Time Limit Exceeded
得分：0
用时：1504 ms
内存：676 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

<10840 bytes omitted>
测试点 #6
Accepted
得分：100
用时：66 ms
内存：676 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
用时：65 ms
内存：660 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
用时：12 ms
内存：1612 KiB

输入文件（8.in） 

1 200000
higlcljtjjezelczszusltndbahanudplnftpxjkyxcapghfkgsvyrclugymaqrrakvnxscwhvlmqqqdmuojlysapv
<349915 bytes omitted>

答案文件（8.out） 

1

用户输出 

1

系统信息 

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

输入文件（10.in） 

1 200000
aidiygcnhnlugueymginpzbrpkygsddmdamadrrqskbclnetprrwazizyiqpngvzlavrakeiszfflbuieywlnxfcdy
<349935 bytes omitted>

答案文件（10.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：46 ms
内存：676 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
Time Limit Exceeded
得分：0
用时：1504 ms
内存：668 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

<14818 bytes omitted>
测试点 #12
Time Limit Exceeded
得分：0
用时：1550 ms
内存：664 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
<16487 bytes omitted>
测试点 #13
Time Limit Exceeded
得分：0
用时：1550 ms
内存：8684 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
<789 bytes omitted>
测试点 #14
Time Limit Exceeded
得分：0
用时：1503 ms
内存：2684 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
<5332 bytes omitted>
CQUPT OJ Powered by SYZOJ.