#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>
#include <queue>
#include <deque>
using namespace std;
map <char,int> a;
map < string , bool > tamga;
map < string , string > tamga2;
pair <int, string > mas[109];
string ans,p,pat,s,s1,word[10]={"oqz","ij","abc","def","gh","kl","mn","prs", "tuv","wxy"};
int main()
{
int n,i,j;
for(i=0;10>i;i++)
{
for(j=0;word[i].length()>j;j++)
a[word[i][j]]=i+1;
}
while(true)
{
cin>>s1;
if(s1.find("-1")==0)break;
cin>>n;
tamga.clear();
tamga2.clear();
for(i=0;n>i;i++)
{
p="";
cin>>s;
for(j=0;s.length()>j;j++)
p+=((a[s[j]]-1)+'0');
tamga[p]=true;
tamga2[p]=s;
}
n=s1.length();
for(i=0;n>i;i++)
{
pat="";
if( i==0 || mas[i-1].first)
for(j=i;n>j;j++)
{
pat+=s1[j];
if(tamga[pat] && i==0){
mas[j]=make_pair( 1,tamga2[pat] );continue;}
if(i==0)continue;
if( tamga[pat] && ( mas[j].first==0 || mas[j].first>mas[i-1].first+1) )
mas[j]=make_pair( mas[i-1].first+1 ,tamga2[pat] );
}
}
if(mas[n-1].first==0 ){cout<<"No solution."<<endl;continue;}
int l=mas[n-1].first;
ans=mas[n-1].second;
mas[n-1]=make_pair(0,"");
l--;
for(i=n-2;i>=0;i--)
{
//cout<<mas[i].first<<" "<<mas[i].second<<endl;
if(mas[i].first==l && l>0){ans=mas[i].second+" "+ans,l--;}
mas[i]=make_pair(0,"");
}
cout<<ans<<endl;
ans="";
}
//system("pause");
return 0;
}
Edited by author 12.11.2013 12:41