#include <iostream>
#include <string>
using namespace std;
const int MAXN = 110;
const int INF = 9999999;

char num[27] = "22233344115566070778889990";
string ans[MAXN][MAXN];
int len, dp[MAXN][MAXN];
char mes[MAXN];

void DP()
{
      for(int i = 1; i<= len; i++) {
          for(int j = 0; j <= len - i; j++) {
               int k = j + i - 1;
               for(int l = j; l < k; l++) {
                     if(dp[j][k] > dp[j][l] + dp[l + 1][k]) {
                          dp[j][k] = dp[j][l] + dp[l + 1][k];
                          ans[j][k] = ans[j][l] + " " + ans[l + 1][k];
                     }
               }
          }
      }
      if(dp[0][len - 1] == INF)
           cout << "No solution" << endl;
      else
           cout << ans[0][len - 1] << endl;
}
                     
int main()
{
      cin >> mes;
      len = strlen(mes);
      memset(dp, 0, sizeof(dp));
      for(int i = 0; i < len; i++)
          for(int j = i; j < len; j++)
               dp[i][j] = INF;
      int n;
      cin >> n;
      char str1[MAXN], str2[MAXN], str3[MAXN];
      for(int i = 0; i < n; i++) {
           cin >> str1;
           strcpy(str2, str1);
           int len1 = strlen(str2);
           for(int j = 0; j < len1; j++)
                str2[j] = num[str2[j] - 'a'];
           str2[len1] = '\0';
           if(strstr(mes, str2) != NULL) {
                //cout << str1 << endl;
                for(int k = 0; k <= len - len1; k++) {
                       strncpy(str3, mes + k, len1);
                       str3[len1] = '\0';
                       if(strcmp(str2, str3) == 0) {
                             //cout << k << "and" << k + len1 - 1 << endl;
                             dp[k][k + len1 - 1] = 1;
                             ans[k][k + len1 - 1] = str1;
                       }
                }
           }
      }
      DP();
      return(0);
}

      

• No solution后面有个“.” (24) 315410110 2009-09-03 19:20:18