对于这题，看到字符串匹配，第一反应想到字符串hash，同时看到$len \leq 8 $ ，考虑对于先给出的n个字符串，O(len2)枚举它的子串，将其加入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
|
#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;
}
}
|
