Submission #00348

ソースコード

?
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
115
#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]);
if(f[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 i = 0; i < M; i++) {
if(slate[i][0] != '*') {
for(int j = 0; j < slen[i]; j++) {
if(slate[i][j] == '*') f[j - 1] = true;
}
}
}
for(int i = 0; i < 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]);
}
fill_n(f, 200, false);
for(int i = 0; i < M; i++) {
if(!last[i]) continue;
for(int j = 0; j < slen[i]; j++) {
if(slate[i][j] == '*') f[j - 1] = true;
}
}
for(int i = 0; i < 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 < M; i++) {
printf("%d\n", ret[i]);
}
}

ステータス

項目 データ
問題 0008 - 石版
ユーザー名 ei1333
投稿日時 2016-08-29 11:41:08
言語 C++11
状態 Memory Limit Exceeded
得点 0
ソースコード長 2553 Byte
最大実行時間 4502 ms
最大メモリ使用量 65536 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00_sample_00.in AC 18 ms 2520 KB
1
01_rand_00.in AC 18 ms 2588 KB
1
01_rand_01.in AC 19 ms 2524 KB
1
01_rand_02.in AC 18 ms 2720 KB
1
01_rand_03.in AC 18 ms 2644 KB
1
01_rand_04.in AC 22 ms 2804 KB
1
01_rand_05.in AC 17 ms 2588 KB
1
01_rand_06.in AC 22 ms 2616 KB
1
01_rand_07.in AC 17 ms 2640 KB
1
01_small_00.in AC 18 ms 2516 KB
1
02_large_00.in AC 51 ms 9748 KB
1
02_large_01.in AC 64 ms 11500 KB
1
02_large_02.in AC 852 ms 54360 KB
1
02_large_03.in MLE 4502 ms 65536 KB
1
03_critical_00.in AC 239 ms 30736 KB
1
03_critical_01.in AC 237 ms 30960 KB
1
77_test_00.in AC 25 ms 3348 KB
1
77_test_01.in AC 23 ms 3424 KB
1
77_test_02.in AC 16 ms 3372 KB
1
77_test_03.in AC 14 ms 3328 KB
1
77_test_04.in AC 19 ms 3412 KB
1
77_test_05.in AC 19 ms 3248 KB
1
77_test_06.in AC 28 ms 3220 KB
1
77_test_07.in AC 22 ms 3196 KB
1
77_test_08.in AC 21 ms 3176 KB
1
77_test_09.in AC 31 ms 3252 KB
1
77_test_10.in AC 20 ms 3332 KB
1
77_test_11.in AC 19 ms 3292 KB
1
77_test_12.in AC 20 ms 3252 KB
1
77_test_13.in AC 15 ms 3220 KB
1
77_test_14.in AC 18 ms 3196 KB
1
77_test_15.in AC 13 ms 3304 KB
1
1000_test_00.in AC 24 ms 3412 KB
1
1000_test_01.in AC 16 ms 3488 KB
1
1000_test_02.in AC 22 ms 3596 KB
1
1000_test_03.in AC 23 ms 3632 KB
1
1000_test_04.in AC 20 ms 3580 KB
1
1000_test_05.in AC 21 ms 3644 KB
1
1000_test_06.in AC 17 ms 3716 KB
1
1000_test_07.in AC 23 ms 3908 KB
1
1000_test_08.in AC 26 ms 3868 KB
1
1000_test_09.in AC 26 ms 3948 KB
1
1000_test_10.in AC 27 ms 4068 KB
1