Description
给出很多个字符串(只有小写字母组成)和很多个提问串,统计出以某个提问串为前缀的字符串数量(单词本身也是自己的前缀).
Input
输入n,表示有n个字符串(n<=10000)
接下来n行,每行一个字符串,字符串度不超过10
输入m,表示有m个提问(m<=100)
第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
Output
对于每个提问,给出以该提问为前缀的字符串的数量.
Sample Input
5
banana
band
bee
absolute
acm
4
ba
b
band
abc
Sample Output
2
3
1
0
sol:方法同Phone list,记下每个结点出现的次数。
1 #include<cstring> 2 #include<iostream> 3 using namespace std; 4 int a[100001][26],tot=1,End[100001]; 5 void ins(char *str) 6 { 7 int n=strlen(str),p=1; 8 for(int i=0;i<n;i++) 9 { 10 int l=str[i]-'a'; 11 if(!a[p][l]) 12 a[p][l]=++tot; 13 p=a[p][l]; 14 End[p]++;//统计结点p出现的次数 15 } 16 } 17 int find(char *str) 18 { 19 int n=strlen(str),p=1; 20 for(int i=0;i<n;i++) 21 { 22 int l=str[i]-'a'; 23 p=a[p][l]; 24 if(!p)return 0; 25 } 26 return End[p]; 27 } 28 char str[11]; 29 int main() 30 { 31 int n,m; 32 scanf("%d",&n); 33 for(int i=1;i<=n;i++) 34 { 35 scanf("%s",str); 36 ins(str); 37 } 38 scanf("%d",&m); 39 for(int i=1;i<=m;i++) 40 { 41 scanf("%s",str); 42 printf("%d ",find(str)); 43 } 44 return 0; 45 }