本文主要是介绍hdu 4287 Intelligent IME 字典树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// hdu 4287 Intelligent IME 字典树
//
// 题目大意：
//
// 智能abc输入法，2,3,4,5,6,7,8,9分别对应不同的字母
// 现在输入n串数字，m串字母串，问n与m对应的串有多少
//
// 解题报告:
//
// 字典树，先将数字插入到字典树中，并赋予val值，最后
// 将字母对应数字，因为字母对应唯一的数字，这样换成数字就
// 可以进行查询了，返回查询结果，计数，over
//
// 感悟：
//
// 开始的时候p的表打错了。。。燃火wa了好几发，我感觉字典树
// 没写错啊，然后仔细看了看题目意思，发现自己想当然了。。。
// 智能abc都忘了。。。哎，不应该啊，继续加油吧~~~FIGHTING!#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int MAX_N = 5008;const int MAX_NODE = 500000;struct Trie{int ch[MAX_NODE][10];int val[MAX_NODE];int sz;void init(){sz = 1;memset(ch[0],0,sizeof(ch[0]));val[0] = 0;}int idx(char c){return c - '0';}void insert(char *s,int v){int u = 0;int n = strlen(s);for (int i=0;i<n;i++){int c = idx(s[i]);if (!ch[u][c]){memset(ch[sz],0,sizeof(ch[sz]));val[sz] = 0;ch[u][c] = sz++;}u = ch[u][c];}val[u] = v;}int query(char *s){int u = 0;int n = strlen(s);for (int i=0;i<n;i++){int c= idx(s[i]);if (!ch[u][c]){return 0;}u = ch[u][c];}return val[u];}}trie;int n,m;char p[30] = "22233344455566677778889999";
char str[8];
int cnt[MAX_N];
void getstr(char *s){for (int i=0;s[i];i++){s[i] = p[s[i]-'a'];}
}
void input(){scanf("%d%d",&n,&m);trie.init();memset(cnt,0,sizeof(cnt));for (int i=1;i<=n;i++){scanf("%s",str);trie.insert(str,i);}for (int i=1;i<=m;i++){scanf("%s",str);getstr(str);//puts(str);cnt[trie.query(str)]++;}for (int i=1;i<=n;i++){printf("%d\n",cnt[i]);}
}int main(){int t;//freopen("1.txt","r",stdin);scanf("%d",&t);while(t--){input(); }return 0;
}
这篇关于hdu 4287 Intelligent IME 字典树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
