In the present world you frequently meet a lot of call numbers and they are going to be longer and longer. You need to remember such a kind of numbers. One method to do it in an easy way is to assign letters to digits as shown in the following picture:
现实生活中，你时常会遇到许多许多而且越来越长的电话号码。你需要记住这类型的号码。 例如按下面的图示，把字母划分到特定的数字上，是一种很容易就能把数字记住的方法：
1 ij 2 abc 3 def
4 gh 5 kl 6 mn
7 prs 8 tuv 9 wxy
0 oqz
This way every word or a group of words can be assigned a unique number, so you can remember words instead of call numbers. It is evident that it has its own charm if it is possible to find some simple relationship between the word and the person itself. So you can learn that the call number 941837296 of a chess playing friend of yours can be read as WHITEPAWN, and the call number 2855304 of your favourite teacher is read BULLDOG.
按这种方法：每个字或一个词组可被代替成一组特定的数字，那么，你只可以通过记住一些词就能记住相应电话号码。 如果可以找出一种单词与个人电话号码的简单关系,它是很有吸引力的。例如你的一个棋友的电话号码是941837296，你可以用 WHITEPAWN来代替；又如你可以用BUULDOG来代替你的一个喜爱的老师的电话号码：2855304。
Problem
Write a program to find the shortest sequence of words (i.e. one having the smallest possible number of words) which corresponds to a given number and a given list of words. The correspondence is described by the picture above.
对给定的给定的数字和单词表，求出一个最简短的单词序列（也就是得出一尽可能短的单词来代替相应的数字）。这种对应关系要求符合上图所描述的关系。
input：
Input contains a series of tests. The first line of each test contains the call number, the transcription of which you have to find. The number consists of at most 100 digits. The second line contains the total number of the words in the dictionary (maximum is 50000). Each of the remaining lines contains one word, which consists of maximally 50 small letters of the English alphabet. The total size of the input file doesn't exceed 300KB. The last line of input file contains call number -1.
输入包含若干组的测试数据。每组测试点的第一行是你所要记住的电话号码。这个号码最多有100个数位。测试的第二行是单词总数（最大为50000个）。以下的每一行是只包含一个单词，单词长度最大限制为50个字母。整个输入文件的大小不超过300KB。 输入文件的最后一行以-1作为结束标志。
output：
Each line of output contains the shortest sequence of words which has been found by your program. The words are separated by single spaces. If there is no solution to the input data, the line contains text `No solution.'. If there are more solutions having the minimum number of words, you can choose any single one of them.
输出文件的每一行为找到的最短单词序列。每个单词间用一个空格隔开。如果没有解决方案，则输出“No solution.”。 如果有多个单词满足条件，可以从中选择任一个单词输出。
input：
7325189087
5
it
your
reality
real
our
4294967296
5
it
your
reality
real
our
-1
output：
reality our
No solution.
【参考程序1】：//模拟而过 如0/1背包一样
#include<iostream>
#include<string>
using namespace std;
struct node
{
string s1;
int len;
} c[50001];
const string Str="22233344115566070778889990";
int n,Len;
int opt[101];
string pre[101];
int main()
{
string ss;
while (true)
{
cin>>ss;
Len=ss.length();
if (ss=="-1") break;
ss=' '+ss;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
cin>>c[i].s1;
c[i].len=c[i].s1.length();
}
for (int i=0;i<=Len;i++)
{
pre[i]="";opt[i]=256;
}
opt[0]=0;
for (int i=1;i<=Len;i++)
for (int j=1;j<=n;j++)
if (i>=c[j].len)
{
bool bk=true;
for (int x=0;x<c[j].len;x++)
{
if (ss[i-x]!=Str[c[j].s1[c[j].len-x-1]-'a'])
{
bk=false;
break;
}
}
if (bk)
if (opt[i]>opt[i-c[j].len]+1)
{
opt[i]=opt[i-c[j].len]+1;
pre[i]=pre[i-c[j].len]+' '+c[j].s1;
}
}
if (opt[Len]!=256)
{
pre[Len].erase(0,1);
cout<<pre[Len]<<endl;
}
else cout<<"No solution."<<endl;
}
return 0;
}
【参考程序2】：DP而过，数据大也不用怕
#include<iostream>
#include<string>
using namespace std;
const string P="22233344115566070778889990";
string path[102][102],s[102];
int opt[102],n,len;
int main()
{
string ss,tt;
while (cin>>ss,ss!="-1")
{
len=ss.size();ss=' '+ss;
cin>>n;
for (int i=1;i<=101;i++)
{
s[i]=""; opt[i]=256;
for (int j=1;j<=101;j++)
path[i][j]="";
}
for (int i=1;i<=n;i++)
{
cin>>tt;
for (int j=1;j<=len;j++)
{
bool bk=true;
for (int k=0;k<tt.size();k++)
if (ss[j-k]!=P[tt[tt.size()-k-1]-'a'])
{
bk=false;
break;
}
if (bk) path[j][tt.size()]=tt;
}
}
string ps;
for (int i=1;i<=len;i++)
if (path[i][i]!="")
{
opt[i]=1;
s[i]=path[i][i];
}
else
{
for (int j=0;j<i;j++)
{
ps=s[i];
if (opt[i]>opt[j]+1 && path[i][i-j]!="")
{
ps=s[j];
opt[i]=opt[j]+1;
ps=ps+' '+path[i][i-j];
}
s[i]=ps;
}
}
if (opt[len]!=256) cout<<ps<<endl;
else cout<<"No solution."<<endl;
}
return 0;
}