查找字符串

時(shí)間限制：1000?ms ?|? 內(nèi)存限制：65535?KB 難度：3 描述

小明得到了一張寫有奇怪字符串的紙，他想知道一些字符串出現(xiàn)了多少次，但這些字符串太多了，他想找你幫忙，你能幫他嗎？輸入字符包括所有小寫字母、‘@’、‘+’。

輸入

第一行包含一個整數(shù)T（T<=100).表示測試數(shù)據(jù)組數(shù)。
接下來每組數(shù)據(jù)第一行包含兩個整數(shù)n，m(n，m<100000),分別表示有n個字符串，小明要問你m次。
接下來n行，每行包含一個字符串，長度不大于15。
接下來m行，每行包含一個字符串，表示小明要問該串出現(xiàn)的次數(shù)。

輸出

輸出每組小明詢問數(shù)串出現(xiàn)的次數(shù)。

樣例輸入1 5 3 hello it@is+so@easy hello ibelieveicanac hello hello icannotacit Giveup 樣例輸出

3 0 0

因?yàn)椤?#43;’的ASCII值是43，‘@’的是64，小寫字母的是97-122之間，‘+’與‘z’相差80，所以每次開辟空間的時(shí)候要開辟80個新的空間。

#include<stdio.h> #include<string.h> #include<stdlib.h> struct node {int cnt;struct node *next[80]; /*80個子節(jié)點(diǎn)*/ }; struct node *root;/*定義根節(jié)點(diǎn)*/ struct node* build() /*建立新的節(jié)點(diǎn)*/ { struct node *p=(node *)malloc(sizeof(node)); /*動態(tài)分配內(nèi)存*/p->cnt=0; for(int i=0;i<80;i++){p->next[i]=NULL; /*新建節(jié)點(diǎn)的子節(jié)點(diǎn)為空*/}return p; } int insert(char*s) {struct node *p=root;int len=strlen(s);for(int i=0;i<len;i++){if(p->next[s[i]-'+']!=NULL)p=p->next[s[i]-'+'];else{p->next[s[i]-'+']=build();p=p->next[s[i]-'+'];}}return p->cnt++; } int search(char *s) {int len=strlen(s);struct node *p=root;for(int i=0;i<len;i++){if(p->next[s[i]-'+']!=NULL)p=p->next[s[i]-'+'];else return 0;}return p->cnt; } int main() {int n,m,t,i;char s1[20],s2[20];scanf("%d",&t);while(t--){root=build();/*建立根節(jié)點(diǎn)*/scanf("%d%d",&n,&m);getchar();for(i=0;i<n;i++){gets(s1);insert(s1);}for(i=0;i<m;i++){gets(s2);printf("%d\n",search(s2));}}return 0; }

其實(shí)就是套用模板。

總結(jié)

以上是生活随笔為你收集整理的NYOJ 685 查找字符串 字典树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。