POJ 1451 T9 （字典树好题）

背景：为了方便九宫格手机用户发短信，希望在用户按键时，根据提供的字典（给出字符串和频数），给出各个阶段最有可能要打的单词。

题意： 首先给出的是字典，每个单词有一个出现频率。然后给出的是询问，每个询问有一个数字字符串，代表在手机上按了哪些键，以1结束。问按键的过程中最可能出现的单词分别是哪些。

思路：搞了很久.......一开始总想着以字母为各结点如何建树，询问......还是太年轻了。

以手机8个键作为字典树各节点，每个结点映射3-4对应的字母。每个结点存频率最高的串，询问的时候也可以方便的直接询问了。

还是太年轻了.........理解题意为具有相同前缀的串的频率是高的覆盖低的........其实是叠加...........一直没看出来。

题目是按照字典序升序给出字典的，所以可以把相同的前缀频率相加，这样只是插入一次了。

接下来就是基本字典树的写法了

 
#include    
#include    
#include    
using namespace std;  
  
char book[] = {"22233344455566677778889999"}; //映射   
char str[1111][111];  
int cou[1111][111];  
struct trie {  
    trie *next[12];  
    char word[105];  
    int num;  
    trie() {  
        num = 0;  
        memset(next,0,sizeof(next));  
        memset(word,0,sizeof(word));  
    }  
}*root;  
  
void insert(char *key,int i)  {  
    trie *p = root;  
    char tmp[105];  
    int ind = 0;  
    int j = 0;  
    while(key[j]) {  
        int t = book[key[j] - 'a'] - '0';  
        tmp[ind++] = key[j];  
        if(p->next[t] == NULL) {  
            p->next[t] = new trie();  
        }  
        p = p->next[t];  
        tmp[ind] = '\0';  
        if(p->num < cou[i][j]) {  
            p->num = cou[i][j];  
            strcpy(p->word,tmp);  
        }  
        j++;  
    }  
}  
  
void query(char *key) {  
    trie *p = root;  
    int flag = 0;  
    while(*key) {  
        int t = *key - '0';  
        if(p->next[t] == NULL || flag) { //用flag标记一下,有可能会有前一个单词不存在，后面单词存在字典中，此时应该输出这个的   
            printf("MANUALLY\n");  
            key++;  
            flag = 1;  
            continue;  
        }  
        p = p->next[t];  
        printf("%s\n",p->word);  
        key ++;  
    }  
}  
  
void free(trie *p) { //释放内存而已   
    for(int i=0; i<=9; i++) {  
        if(p->next[i] != NULL) free(p->next[i]);  
    }  
    delete p;  
}  
  
int main() {  
#ifndef ONLINE_JUDGE   
    freopen("in.txt","r",stdin);  
    freopen("D:\\hehe.txt","w",stdout);  
#endif   
    int T,cnt;  
    cin >> T;  
    int casee = 1;  
    while(T --) {  
        root = new trie();  
        int n,i;  
        scanf("%d",&n);  
        for(i=0; i