POJ 1451 T9 （字典樹好題）

背景：為了方便九宮格手機用戶發短信，希望在用戶按鍵時，根據提供的字典（給出字符串和頻數），給出各個階段最有可能要打的單詞。

題意： 首先給出的是字典，每個單詞有一個出現頻率。然後給出的是詢問，每個詢問有一個數字字符串，代表在手機上按了哪些鍵，以1結束。問按鍵的過程中最可能出現的單詞分別是哪些。

思路：搞了很久.......一開始總想著以字母為各結點如何建樹，詢問......還是太年輕了。

以手機8個鍵作為字典樹各節點，每個結點映射3-4對應的字母。每個結點存頻率最高的串，詢問的時候也可以方便的直接詢問了。

還是太年輕了.........理解題意為具有相同前綴的串的頻率是高的覆蓋低的........其實是疊加...........一直沒看出來。

題目是按照字典序升序給出字典的，所以可以把相同的前綴頻率相加，這樣只是插入一次了。

接下來就是基本字典樹的寫法了

 
#include <cstdio>   
#include <cstring>   
#include <iostream>   
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<n; i++) {  
            scanf("%s%d",str[i],&cnt);  
            int len = strlen(str[i]);  
            for(int j=0; j<len; j++) {  
                cou[i][j] = cnt;  
            }  
        }  
        for(i=1; i<n; i++) //相同前綴頻率相加，堆在一起算   
            for(int j=0; str[i][j] && str[i - 1][j]; j++) {  
                if(str[i][j] == str[i-1][j]) {  
                    cou[i][j] += cou[i-1][j];  
                    cou[i-1][j] = 0;  
                }  
                else break;  
            }  
        for(i=0; i<n; i++) {  
            insert(str[i],i);  
        }  
        printf("Scenario #%d:\n",casee ++);  
        int m;  
        scanf("%d",&m);  
        char str1[111],st[111];  
        for(i=0; i<m; i++) {  
            scanf("%s",st);  
            int len = strlen(st);  
            strncpy(str1,st,len-1);  
            str1[len-1] = '\0';  
            query(str1);  
            puts("");  
        }  
        puts("");  
        free(root);  
    }  
    return 0;  
}