题目回顾

我们需要实现一个T9文本输入系统，该系统能够根据用户按下的数字键（2-9）实时预测最可能的单词前缀。系统基于一个内置字典，字典中的每个单词都有一个概率值。预测的规则是：每次按键后，显示当前数字序列对应的所有可能前缀中概率总和最大的那个。如果多个前缀概率相同，则选择字典序最小的那个。如果没有任何匹配的前缀，则输出"MANUALLY"。

解题思路

1. 数据结构选择：使用字典树（Trie）来存储字典中的单词及其概率。字典树能够高效地处理前缀匹配问题。
2. 按键映射：将数字键2-9映射到对应的字母集合（如2对应a、b、c）。
3. 概率计算：对于每个数字序列，计算所有可能前缀的概率总和，并选择最大的那个。
4. 查询处理：对于每个输入的数字序列（以1结尾），逐步处理每个数字，实时更新当前最可能的前缀。

复杂度分析

• 时间复杂度：
  • 插入单词：O(L)，其中L是单词长度。
  • 查询数字序列：O(4^D)，其中D是数字序列长度（最坏情况，但实际中由于字典树剪枝，效率较高）。
• 空间复杂度：O(N*26)，其中N是字典树节点数。 ###代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
struct node{
	int val[26];//26个儿子每个儿子的权值 
	int ch[26];//26个儿子 
}tr[100005];//字典树 
int check[10][4]={
	{0,0,0,0},
	{0,0,0,0},
	{0,1,2,26},
	{3,4,5,26},
	{6,7,8,26},
	{9,10,11,26},
	{12,13,14,26},
	{15,16,17,18},
	{19,20,21,26},
	{22,23,24,25}};//建立一个类似于按键表的东西 
char s[105],t[105],ans[105][105];
int flag[105],n,m,tot;
void newnode(int x,int tmp,int v)//增加新节点 
{
	if (v) tr[x].ch[tmp]=++tot;
	else tr[x].ch[tmp]=0;
	tr[x].val[tmp]+=v;
	for (int i=0;i<26;i++)//防多组数据，初始化 
		tr[tot].val[i]=0,tr[tot].ch[i]=0;
}
void insert(int v)//建字典树 
{
	//这里的s是输入的单词 
	int len=strlen(s);
	int now=0;
	for (int i=0;i<len;i++)
	{
		int tmp=s[i]-'a';
		if (tr[now].ch[tmp]) tr[now].val[tmp]+=v;
		else newnode(now,tmp,v);
		now=tr[now].ch[tmp];
	}
}
void query(int id,int dep)//查询 
{
	//这里的s是输入的一串按键 
	if (strlen(s)-1==dep) return ;
	for (int i=0;i<4;i++)
	{
		int tmp=check[s[dep]-'0'][i];
		if (tr[id].ch[tmp])
		{
			t[dep]=tmp+'a';
			t[dep+1]='\0';
			if ( !flag[dep] || tr[id].val[tmp]>flag[dep])
			{
				flag[dep]=tr[id].val[tmp];
				strcpy(ans[dep],t);
			}
			query(tr[id].ch[tmp],dep+1);
		}
	}
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		printf("Scenario #%d:\n",i); tot=0;
		newnode(0,0,0);
		scanf("%d",&m);
		for (int j=1;j<=m;j++)
		{
			int vvv;
			scanf("%s%d",s,&vvv);
			insert(vvv);
		}
		scanf("%d",&m);
		for (int j=1;j<=m;j++)
		{
			scanf("%s",s);
			memset(flag,0,sizeof(flag));
			query(0,0);
			int len=strlen(s);
			for (int k=0;k<len-1;k++)
				if (flag[k]) printf("%s\n",ans[k]);
			else printf("MANUALLY\n");
			printf("\n");
		}
		printf("\n");
	}
}