Submission #00353

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
using namespace std;
const int base1 = 1007;
const int base2 = 1009;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
typedef pair< int, int > T;
int N, M;
char word[100000][201];
char slate[100000][201];
int wlen[100000], slen[100000];
map< T, int > hashh[201];
set< T > ended[201];
int ret[100000];
bool last[100000];
bool f[200];
T commit(const T& p, char c)
{
return (make_pair(1LL * (p.first + c) * base1 % mod1,
1LL * (p.second + c) * base2 % mod2));
}
void create(int idx)
{
T hashed = {0, 0};
for(int i = 0; i < wlen[idx]; i++) {
hashed = commit(hashed, word[idx][i]);
hashh[i][hashed]++;
}
ended[wlen[idx]].insert(hashed);
}
int count(char *s, int idx, T t)
{
if(s[idx] == '\0') {
return (ended[idx].find(t) != ended[idx].end());
} else if(s[idx] == '?') {
int ret = 0;
for(char i = 'a'; i <= 'z'; i++) ret += count(s, idx + 1, commit(t, i));
return (ret);
} else if(s[idx] == '*') {
if(hashh[idx - 1].find(t) != hashh[idx - 1].end()) return (hashh[idx - 1][t]);
return (0);
} else {
return (count(s, idx + 1, commit(t, s[idx])));
}
}
int main()
{
scanf("%d %d", &N, &M);
for(int i = 0; i < N; i++) {
scanf(" %s", word[i]);
wlen[i] = strlen(word[i]);
}
for(int i = 0; i < M; i++) {
scanf(" %s", slate[i]);
slen[i] = strlen(slate[i]);
}
for(int k = 0; k < N; k += 1000) {
for(int i = k; i < min(k + 1000, N); i++) {
create(i);
}
for(int i = 0; i < M; i++) {
if(slate[i][0] != '*') {
ret[i] += count(slate[i], 0, make_pair(0, 0));
} else {
last[i] = true;
}
}
for(int i = 0; i < 201; i++) {
hashh[i].clear();
ended[i].clear();
}
}
for(int i = 0; i < N; i++) {
reverse(word[i], word[i] + wlen[i]);
}
for(int i = 0; i < M; i++) {
if(!last[i]) continue;
reverse(slate[i], slate[i] + slen[i]);
}
for(int k = 0; k < N; k += 1000) {
for(int i = k; i < min(k + 1000, N); i++) {
create(i);
}
for(int i = 0; i < M; i++) {
if(last[i]) {
ret[i] += count(slate[i], 0, make_pair(0, 0));
}
}
for(int i = 0; i < 201; i++) {
hashh[i].clear();
ended[i].clear();
}
}
for(int i = 0; i < M; i++) {
printf("%d\n", ret[i]);
}
}

ステータス

項目 データ
問題 0008 - 石版
ユーザー名 ei1333
投稿日時 2016-08-29 11:44:15
言語 C++11
状態 Accepted
得点 16
ソースコード長 2448 Byte
最大実行時間 4025 ms
最大メモリ使用量 29456 KB

セット

セット 得点 Cases
1 ALL 16 / 16 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00_sample_00.in AC 18 ms 2524 KB
1
01_rand_00.in AC 21 ms 2588 KB
1
01_rand_01.in AC 24 ms 2524 KB
1
01_rand_02.in AC 20 ms 2588 KB
1
01_rand_03.in AC 16 ms 2640 KB
1
01_rand_04.in AC 20 ms 2676 KB
1
01_rand_05.in AC 18 ms 2584 KB
1
01_rand_06.in AC 16 ms 2616 KB
1
01_rand_07.in AC 22 ms 2772 KB
1
01_small_00.in AC 16 ms 2640 KB
1
02_large_00.in AC 94 ms 8076 KB
1
02_large_01.in AC 118 ms 8248 KB
1
02_large_02.in AC 970 ms 24496 KB
1
02_large_03.in AC 1189 ms 24668 KB
1
03_critical_00.in AC 3767 ms 29248 KB
1
03_critical_01.in AC 4025 ms 29456 KB
1
77_test_00.in AC 17 ms 3464 KB
1
77_test_01.in AC 19 ms 3408 KB
1
77_test_02.in AC 16 ms 3356 KB
1
77_test_03.in AC 21 ms 3440 KB
1
77_test_04.in AC 18 ms 3388 KB
1
77_test_05.in AC 24 ms 3228 KB
1
77_test_06.in AC 24 ms 3456 KB
1
77_test_07.in AC 19 ms 3428 KB
1
77_test_08.in AC 17 ms 3400 KB
1
77_test_09.in AC 14 ms 3476 KB
1
77_test_10.in AC 30 ms 3552 KB
1
77_test_11.in AC 18 ms 3388 KB
1
77_test_12.in AC 20 ms 3344 KB
1
77_test_13.in AC 21 ms 3444 KB
1
77_test_14.in AC 16 ms 3416 KB
1
77_test_15.in AC 20 ms 3388 KB
1
1000_test_00.in AC 18 ms 3496 KB
1
1000_test_01.in AC 19 ms 3668 KB
1
1000_test_02.in AC 21 ms 3772 KB
1
1000_test_03.in AC 23 ms 3804 KB
1
1000_test_04.in AC 29 ms 3876 KB
1
1000_test_05.in AC 21 ms 3932 KB
1
1000_test_06.in AC 19 ms 4004 KB
1
1000_test_07.in AC 18 ms 3932 KB
1
1000_test_08.in AC 25 ms 4012 KB
1
1000_test_09.in AC 24 ms 4080 KB
1
1000_test_10.in AC 23 ms 4192 KB
1