题意：
给定一串数字，问这串数字可能代表的单词，若存在多个可能，输出单词数最少的情况，若还是相同输出任意符合的单词。数字转换规则就是根据手机的按键规则。
题解：
我们将所有单词转换成数字，然后保存到字典树中。然后开始dp给定的数字串,dp[i]表示从i开始到最后的数字串最少需要多少个单词构成。dp[i]=min(dp[k+1])（m>k>=i，且[i,k]数字串在字典树中存在）。由于要输出单词，所以用pre[i]记录i位置的下个单词位置，num[i]记录i位置后的单词编号。
代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
using namespace std;
#define LL long long
const int maxn=50001*51;
const int INF=1e8;
int f[27]={2,2,2,3,3,3,4,4,1,1,5,5,6,6,0,7,0,7,7,8,8,8,9,9,9,0};
struct Trie{
int ch[maxn][10];
int val[maxn];
int sz;
Trie(){sz=1;memset(ch[0],0,sizeof(ch[0]));}
int idx(char c)
{
return f[c-'a'];
}
void insert(char *s,int v)
{
int i,u=0,n=strlen(s);
for(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;
}
}e;
char a[50005][55];
char str[110];
int pre[110],num[110],dp[110],g[110],gg;
int main()
{
while(scanf("%s",str)!=EOF)
{
if(str[0]=='-')break;
int n;
scanf("%d",&n);
int i,j,k,u,m;
memset(e.ch[0],0,sizeof(e.ch[0]));
e.sz=1;
for(i=1;i<=n;i++)
{
scanf("%s",a[i]);
e.insert(a[i],i);
}
memset(pre,-1,sizeof(pre));
m=strlen(str);
dp[m]=0;
for(i=0;i<m;i++)dp[i]=INF;
for(i=m-1;i>=0;i--)
{
u=0;
for(j=i;j<m;j++)
{
int c=str[j]-'0';
if(!e.ch[u][c])break;
u=e.ch[u][c];
if(e.val[u])
{
if(dp[i]>dp[j+1]+1)
{
dp[i]=dp[j+1]+1;
pre[i]=j+1;
num[i]=e.val[u];
}
}
}
}
if(dp[0]==INF)printf("No solution.\n");
else
{
gg=0;
k=0;
while(pre[k]!=-1)
{
g[gg++]=num[k];
k=pre[k];
}
for(i=0;i<gg;i++)
{
if(i==gg-1)printf("%s\n",a[g[i]]);
else printf("%s ",a[g[i]]);
}
}
}
return 0;
}
/*
2
than
that
*/
