#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int table[256];
string num;
int n;
string word[1 << 16];
string r[1 << 16];
int place[1 << 16][2];
int dp[2128];
string convert(string a){
    for ( int i = 0; i < a.size(); ++i )
        a[i] = table[a[i]];
    return a;
}
bool f( string a, string b ){
    return a.size() > b.size();
}
void scan(){
    cin >> n;
    for ( int i = 0; i < n; ++i ){
        cin >> word[i];
        r[i] = word[i];
        word[i] = convert(word[i]);
//        cout << word[i] << "\n";
    }
    sort(word, word + n, f );
    sort(r,r+n, f);
}
void fill(){
    table['i'] = table['j'] = '1';
    table['a'] = table['b'] = table[ 'c' ] = '2';
    table['d'] = table['e'] = table[ 'f' ] = '3';
    table['g'] = table['h'] = '4';
    table['k'] = table['l'] = '5';
    table['m'] = table['n'] = '6';
    table['p'] = table['r'] = table[ 's' ] = '7';
    table['t'] = table['u'] = table[ 'v' ] = '8';
    table['w'] = table['x'] = table[ 'y' ] = '9';
    table['o'] = table['q'] = table[ 'z' ] = '0';
}
void solve(){
    memset(dp,0,sizeof(dp));
    dp[0] = 1;
    vector <string> ans[128];
    for ( int i = 1; i <= num.size(); ++i )
        for(int j = 0; j < n; ++j ){
            if ( i - word[j].size() < 0 )continue;
            if ( dp[i - word[j].size()] && num.substr(i - word[j].size(), word[j].size()) == word[j]
            &&((dp[i-word[j].size()] + 1 < dp[i])||!dp[i])){
                dp[i] = dp[i - word[j].size()] + 1;
                ans[i] = ans[i - word[j].size()];
                ans[i].push_back(r[j]);
        }
    }
    if ( !ans[num.size()].size() ) ans[num.size()].push_back("No solution.");
    for ( int i = 0; i < ans[num.size()].size(); ++i )
        cout << ans[num.size()][i] << " ";
    cout << endl;
}
int main(){
    fill();
    char ch;
    cin >> num;
    while ( num != "-1"){
    scan();
    solve();
    cin >> num;
    }
}
I tried and tried... but I can't find my stupid mistake... Maybe you'll find it... Please help!

Edited by author 14.01.2009 03:09

Edited by author 14.01.2009 03:09

Edited by author 14.01.2009 03:10