题目链接： ,刚学的字典树，就当模板了。

　　最近都没有好好刷题，罪过罪过。

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;#define LL long longconst int maxn = 1000000;struct Trie { int ch[maxn][26]; int cnt[maxn]; int size; Trie() { size = 1; memset(ch[0] , 0 , sizeof(ch[0])); memset(cnt , 0 , sizeof(cnt)); } int index(char c) { return c - 'a'; } void insert(char *s , int v) { int i , u; for(i = u = 0 ; s[i] != '\0' ; i++) { int c = index(s[i]); if(!ch[u][c]) {　 memset(ch[size] , 0 , sizeof(ch[size])); ch[u][c] = size++; } u = ch[u][c]; cnt[u]++; //必须在这里 } } int query(char *s) { int i , u; for(i = u = 0 ; s[i] != '\0' ; i++) { int c = index(s[i]); if(!ch[u][c]) return 0; u = ch[u][c]; } return cnt[u]; }} trie;int main() { int n , m; char s[20]; scanf("%d" , &n); while(n--) { scanf("%s" , s); trie.insert(s , 1); } scanf("%d" , &m); while(m--) { scanf("%s" , s); printf("%d\n" , trie.query(s)); }}