本文主要是介绍POJ 1451 字典树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这题的意思有点类似于一个输入法，就是按了一些键，蹦出单词库中频率最高的那个词汇
首先给出的是单词库，每个单词有一个出现频率。
然后给出的是一些询问，每个询问有一个字符串，代表在手机上按了哪些键，最后以1结束。问进行这些按键的过程中出现的单词分别是哪些。
思路就是字典树了。
以手机的8个键做8个指针来建立字典树。
每个结点存的除了指针外，还有出现频率最高的单词。
建树的时候需要注意，每个相同的前缀只能插入一次，否则就没法处理。
所以插入之前，把所有相同前缀的频率值都加起来 ，插入的时候插一次就好了，每次更新最优值就行。
题目给的输入是已经排好序的，也就省了我们排序的时间。因为前缀相同的肯定在一块，所以挨个同相邻的比较就行了、
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 1111
#define MAXM 55555
#define INF 1000000000
using namespace std;
int c[1005][105], e;
char s[1005][105];
char tmp[105];
char dic[] = "22233344455566677778889999";
struct Trie
{int next[8];int num;char s[105];void init (){memset(next, 0, sizeof(next));num = 0;}
} trie[MAXM];
void make_trie (char *str, int id)
{int i = 0, index, u = 0;while(str[i]){index = dic[str[i] - 'a'] - '2';if(!trie[u].next[index]) trie[u].next[index] = ++e;u = trie[u].next[index];if(c[id][i] > trie[u].num){trie[u].num = c[id][i];for(int j = 0; j <= i; j++) trie[u].s[j] = s[id][j];trie[u].s[i + 1] = '\0';}i++;}
}
void match(char *str)
{int i = 0, index, u = 0, flag = 0;;while(str[i] && str[i] != '1'){index = str[i] - '2';u = trie[u].next[index];if(trie[u].num == 0 || u == 0 || flag) printf("MANUALLY\n"), flag = 1;else printf("%s\n", trie[u].s);i++;}
}
int main()
{int T, n, p, m, cas = 0;scanf("%d", &T);while(T--){scanf("%d", &n);memset(c, 0, sizeof(c));for(int i = 0; i < n; i++){scanf("%s%d", s[i], &p);int len = strlen(s[i]);for(int j = 0; j < len; j++) c[i][j] = p;}for(int i = 1; i < n; i++)for(int j = 0; s[i][j] && s[i - 1][j]; j++){if(s[i][j] == s[i - 1][j]){c[i][j] += c[i - 1][j];c[i - 1][j] = 0;}else break;}for(int i = 0; i < MAXM; i++) trie[i].init();e = 0;for(int i = 0; i < n; i++) make_trie(s[i], i);scanf("%d", &m);printf("Scenario #%d:\n", ++cas);while(m--){scanf("%s", tmp);match(tmp);printf("\n");}printf("\n");}return 0;
}
这篇关于POJ 1451 字典树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
