http://acm.hdu.edu.cn/showproblem.php?pid=1251 题目大意：给你一个字符串列表，后边给出一些字符串，查询这些字符串作为前缀出现过多少次
字典树解法
#include <bits/stdc++.h> #define N 26 using namespace std; struct Trie { int cnt; Trie *next[N]; Trie() { cnt = 0; for(int i=0;i<N;i++) next[i] = NULL; } }; Trie *root,*current,*temp; void insert(string str)//构造字典树 { current = root; for(int i=0;i<str.length();i++) { if(current->next[str[i]-'a'] == NULL) { temp = new Trie; current->next[str[i] - 'a'] = temp; current = current->next[str[i] - 'a']; } else current = current->next[str[i]-'a']; current->cnt++;//每次出现这个字母次数加一 } } int search(char str[])//查询操作，扫描这个字符串，如果有个字符没有出现在字符串中就返回0，否则就返回这个字符串出现的次数 { current = root; int i; for(i=0; current!=NULL&&i<strlen(str); i++) { current = current->next[str[i]-'a']; } if(current != NULL&¤t->cnt>0)// return current->cnt; return 0; } void del(Trie *root) { for(int i=0;i<N;i++) if(root->next[i]!=NULL) del(root->next[i]); delete(root); } int main() { string str; char s[15]; root = new Trie; while(getline(cin,str)) { int len = str.length(); if(len == 0) break; insert(str); } while(~scanf("%s",s)) { printf("%d\n",search(s)); } del(root); return 0; }map：
#include <iostream> #include <string.h> #include <string> #include <map> using namespace std; int main() { string s,str; map<string,int> m; while(getline(cin,s)) { int l=s.length(); if(l==0) break; for(int i=1;i<=s.length();i++) { string s1=s.substr(0,i); m[s1]++; } } while(cin>>str) { cout<<m[str]<<endl; } //cout << "Hello world!" << endl; return 0; }