对于这题,看到字符串匹配,第一反应想到字符串hash,同时看到$len \leq 8 $ ,考虑对于先给出的$n$个字符串,$O(len^2)$枚举它的子串,将其加入$map$中,但是要注意如果一个然后对于每个字符串,我们都统计一下它最后一次出现在哪里(于是就可以顺便判一下重)

然后我们在询问的时候,就可以直接输出这个字符串对应的出现次数以及最后一处出现的位置啦QwQ

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
// Sooke bless me.
// LJC00118 bless me.
#include<bits/stdc++.h>

#define INF 2147483647
#define ll long long

int Inp(){
char c = getchar();
int Neg = 1;
while(c < '0' || c > '9'){
if(c == '-')
Neg = -1;
c = getchar();
}
int Sum = 0;
while(c >= '0' && c <= '9'){
Sum = ((Sum << 3) + (Sum << 1)) + c - '0';
c = getchar();
}
return Neg * Sum;
}

std::map <std::string, int> Cnt; // 出现次数
std::map <std::string, int> Ans; // 最后一次出现位置
std::string s[10010];

int main(){
int n = Inp();
for(int i = 1; i <= n; i++){
std::cin >> s[i];
int Len = s[i].size();
for(int j = 1; j <= Len; j++)
for(int u = 0; u <= Len - j; u++){
if(Ans[s[i].substr(u, j)] != i){
Cnt[s[i].substr(u, j)]++;
Ans[s[i].substr(u, j)] = i;
}
}
}
int m = Inp();
for(int i = 1; i <= m; i++){
std::string str;
std::cin >> str;
printf("%d ", Cnt[str]);
if(Cnt[str] == 0)
printf("-\n");
else
std::cout << s[Ans[str]] << std::endl;
}
}

 评论