[HIHO1260]String Problem I（trie树）

题目链接：http://hihocoder.com/problemset/problem/1260

n个字符串，m次询问。每次询问给一个字符串，问这个字符串仅可以在一个地方加一个字母。这样操作后与n个字符串中有多少个字符串一样。

trie树维护n个字符串，然后从根节点向下dfs。

 #include <algorithm>

 #include <iostream>

 #include <iomanip>

 #include <cstring>

 #include <climits>

 #include <complex>

 #include <fstream>

 #include <cassert>

 #include <cstdio>

 #include <bitset>

 #include <vector>

 #include <deque>

 #include <queue>

 #include <stack>

 #include <ctime>

 #include <set>

 #include <map>

 #include <cmath>

 using namespace std;

 typedef struct Node {

     Node *next[];

     int cnt;

     Node() {

         cnt = ;

         for(int i = ; i < ; i++) {

             next[i] = NULL;

         }

     }

 }Node;

 void insert(Node *p, char *str) {

     for(int i = ; str[i]; i++) {

         int t = str[i] - 'a';

         if(p->next[t] == NULL) {

             p->next[t] = new Node();

         }

         p = p->next[t];

     }

     p->cnt++;

 }

 int len, cnt;

 void dfs(Node *p, char *str, int cur, int flag) {

     if(flag > ) return;

     if(cur == len && flag == ) {

         cnt++;

         return;

     }

     for(int i = ; i < ; i++) {

         if(p->next[i]) {

             // printf("%c\n", 'a'+i);

             if('a' + i == str[cur]) {

                 dfs(p->next[i], str, cur+, flag);

             }

             else {

                 if(flag > ) continue;

                 dfs(p->next[i], str, cur, flag+);

             }

         }

     }

 }

 void del(Node *root) {

     for(int i = ; i < ; i++) {

         if(root->next[i] != NULL) {

             del(root->next[i]);

         }

     }

     delete root;

 }

 const int maxn = ;

 int n, m;

 char tmp[maxn];

 int main() {

     // freopen("in", "r", stdin);

     while(~scanf("%d %d", &n, &m)) {

         Node *root = new Node();

         for(int i = ; i < n; i++) {

             scanf("%s", tmp);

             insert(root, tmp);

         }

         for(int i = ; i < m; i++) {

             scanf("%s", tmp);

             len = strlen(tmp);

             cnt = ;

             dfs(root, tmp, , );

             printf("%d\n", cnt);

         }

         del(root);

     }

     return ;

 }