Repository
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 5048 Accepted Submission(s): 1739
Problem Description
When
you go shopping, you can search in repository for avalible merchandises
by the computers and internet. First you give the search system a name
about something, then the system responds with the results. Now you are
given a lot merchandise names in repository and some queries, and
required to simulate the process.
Input
There
is only one case. First there is an integer P
(1<=P<=10000)representing the number of the merchanidse names in
the repository. The next P lines each contain a string (it's length
isn't beyond 20,and all the letters are lowercase).Then there is an
integer Q(1<=Q<=100000) representing the number of the queries.
The next Q lines each contains a string(the same limitation as foregoing
descriptions) as the searching condition.
Output
For each query, you just output the number of the merchandises, whose names contain the search string as their substrings.
Sample Input
20
ae
af
ag
ah
ai
aj
ak
al
ads
add
ade
adf
adg
adh
adi
adj
adk
adl
aes
5
b
a
d
ad
s
Sample Output
0
20
11
11
2
我好气呀 g++无限爆内存 换c++过了 无奈下顺便写了个静态的
题意就是有n个字符串，m个询问 问字符串在n个字符串中出现过多少次
比如 abcd 中有a,b,c,d,abcd,bcd,cd,bc,abc...
我们可以将abcd拆成abcd bcd cd d 分别建树，每个字符计算下数字
但abab会导致重复，所以我们设置一下标记，看代码
动态建树，g++爆内存 c++交
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<queue> 7 #include<map> 8 #include<set> 9 #include<vector> 10 #include<cstdlib> 11 #include<string> 12 #define eps 0.000000001 13 typedef long long ll; 14 typedef unsigned long long LL; 15 using namespace std; 16 struct tire{ 17 int id,num; 18 tire *next[26]; 19 }; 20 tire *root; 21 void insert(char *s,int k){ 22 tire *p,*q; 23 p=root; 24 int len=strlen(s); 25 for(int i=0;i<len;i++){ 26 //cout<<3<<endl; 27 int t=s[i]-'a'; 28 if(p->next[t]==NULL){ 29 q=(tire *)malloc(sizeof(tire)); 30 for(int j=0;j<26;j++)q->next[j]=NULL; 31 q->num=0; 32 q->id=-1; 33 p->next[t]=q; 34 } 35 p=p->next[t]; 36 if(p->id!=k){ 37 p->id=k; 38 p->num++; 39 } 40 } 41 } 42 int find(char *s){ 43 tire *p=root; 44 int len=strlen(s); 45 for(int i=0;i<len;i++){ 46 int t=s[i]-'a'; 47 if(p->next[t]==NULL)return 0; 48 else 49 p=p->next[t]; 50 } 51 return p->num; 52 } 53 int main(){ 54 int m,n; 55 char str[22]; 56 root=(tire *)malloc(sizeof(tire)); 57 for(int i=0;i<26;i++)root->next[i]=NULL; 58 root->id=-1; 59 root->num=0; 60 scanf("%d",&n); 61 for(int i=0;i<n;i++){ 62 scanf("%s",str); 63 int len=strlen(str); 64 for(int j=0;j<len;j++){ 65 //cout<<1<<endl; 66 insert(str+j,i);//cout<<2<<endl; 67 } 68 } 69 scanf("%d",&m); 70 while(m--){ 71 scanf("%s",str); 72 cout<<find(str)<<endl; 73 } 74 }
接下来是一个静态的字典树（节省内存） c++ g++都可以过
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<cstdlib> #include<string> #define maxnode 500000 #define sigma_size 30 #define eps 0.000000001 typedef long long ll; typedef unsigned long long LL; using namespace std; int ch[maxnode][sigma_size]; int val[maxnode]; int flag[maxnode]; int sz; void init(){ memset(ch[0],0,sizeof(ch[0])); sz=1; } int idx(char c){ return c-'a'; } void insert(char *s,int k){ int u=0; int len=strlen(s); for(int i=0;i<len;i++){ int c=idx(s[i]); if(ch[u][c]==0){ memset(ch[sz],0,sizeof(ch[sz])); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; if(flag[u]!=k){ val[u]++; flag[u]=k; } } } int find(char *s){ int u=0; int len=strlen(s); for(int i=0;i<len;i++){ int c=idx(s[i]); if(ch[u][c]==0)return 0; u=ch[u][c]; } return val[u]; } int main(){ int m,n; init(); memset(flag,-1,sizeof(flag)); //for(int i=0;i<10;i++)cout<<flag[i]<<" "; char str[100]; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%s",str); int len=strlen(str); for(int j=0;j<len;j++){ //cout<<1<<endl; insert(str+j,i);//cout<<2<<endl; } } scanf("%d",&m); while(m--){ scanf("%s",str); cout<<find(str)<<endl; } }
Source