http://acm.hdu.edu.cn/showproblem.php?pid=1251

題意: 找前綴數量 裸模板

?

1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 const int maxn=500010; 9 const double eps=1e-8; 10 const long long modn=1000; 11 struct tri{ 12 int count; 13 int next[26]; 14 bool exist; 15 }e[maxn]; 16 char a[20]={}; 17 int tot=0; 18 void doit(int x,int k,int j){ 19 e[x].count++; 20 if(k<j){ 21 e[x].exist=1; 22 return; 23 } 24 int w=a[j]-'a'; 25 if(!e[x].next[w]){ 26 e[x].next[w]=++tot; 27 doit(tot,k,j+1); 28 }else{ 29 doit(e[x].next[w],k,j+1); 30 } 31 } 32 int getit(int x,int k,int j){ 33 if(k<j){ 34 return e[x].count; 35 } 36 int w=a[j]-'a'; 37 if(!e[x].next[w]){ 38 return 0; 39 } 40 else{ 41 return getit(e[x].next[w],k,j+1); 42 } 43 } 44 int main(){ 45 memset(e,0,sizeof(e)); 46 a[0]=getchar(); 47 while(1){ 48 int i=1;a[i]=getchar(); 49 while(a[i]!='\n'){ 50 i++; 51 a[i]=getchar(); 52 } 53 doit(0,i-1,0); 54 a[0]=getchar(); 55 if(a[0]=='\n'){ 56 break; 57 } 58 } 59 while(~scanf("%s",&a)){ 60 int z=strlen(a)-1; 61 printf("%d\n",getit(0,z,0)); 62 } 63 return 0; 64 } View Code

?

轉載于:https://www.cnblogs.com/137shoebills/p/7786487.html

總結

以上是生活随笔為你收集整理的HDU1251 统计难题 trie树 简单的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。