SHARE
TWEET

Untitled

a guest Jan 24th, 2020 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <iostream>
  3. #include <map>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. map <vector <int>, pair <vector <int>, int>> dfs_list;
  9. map <vector <int>, int> numb;
  10. vector <int> o(26);
  11. pair <vector<int>, int> o1(o, 1);
  12.  
  13. pair <vector <int>, int> dfs( vector <int> a )
  14. {
  15.     if( dfs_list[a].second )
  16.         return dfs_list[a];
  17.     else
  18.         {
  19.             int s = 0;
  20.             int i;
  21.             for( i = 0; i < 26; i++ )
  22.                 s+=a[i];
  23.             if( s == 1 )
  24.                 dfs_list[a] = o1;
  25.             else
  26.                 {
  27.                     s = 0;
  28.                     vector <int> u(26);
  29.                     map <int, vector <int>> mas;
  30.                     for( i = 0; i < 26; i++ )
  31.                         if( a[i] )
  32.                         {
  33.                             u = a;
  34.                             u[i]--;
  35.                             if( numb[u] )
  36.                             {
  37.                                 mas[s] = u;
  38.                                 s++;
  39.                             }
  40.                         }
  41.                     if( !s )
  42.                         dfs_list[a] = o1;
  43.                     else
  44.                     {
  45.                         int k = 0;
  46.                         int ways[s];
  47.                         for( i = 0; i < s; i++ )
  48.                             ways[i] = dfs( mas[i] ).second;
  49.                         int l = ways[0];
  50.                         for( i = 1; i < s; i++ )
  51.                             if( ways[i] > l )
  52.                             {
  53.                                 l = ways[i];
  54.                                 k = i;
  55.                             }
  56.                         dfs_list[a] = make_pair(mas[k], ways[k]+1);
  57.                     }
  58.                 }
  59.             return dfs_list[a];
  60.         }
  61. }
  62.  
  63. int main()
  64. {
  65.     cin.tie(0);
  66.     ios_base::sync_with_stdio(0);
  67.     int n;
  68.     cin >> n;
  69.     vector<string> plate_words(n);
  70.     vector<vector<int>> plate_vectors(n);
  71.     int k;
  72.     int i;
  73.     for( k = 0; k < n; k++ )
  74.     {
  75.         cin >> plate_words[k];
  76.         plate_vectors[k].resize(26);
  77.         for( i = 0; i < plate_words[k].length(); i++ )
  78.             plate_vectors[k][plate_words[k][i]-'a']++;
  79.     }
  80.     int m;
  81.     cin >> m;
  82.     vector<string> dict_words(m);
  83.     vector<vector<int>> dict_vectors(m);
  84.     for( k = 0; k < m; k++ )
  85.     {
  86.         cin >> dict_words[k];
  87.         dict_vectors[k].resize(26);
  88.         for( i = 0; i < dict_words[k].length(); i++ )
  89.             dict_vectors[k][dict_words[k][i]-'a']++;
  90.         numb[dict_vectors[k]] = k + 1;
  91.     }
  92.     for( k = 0; k < n; k++ )
  93.     {
  94.         int f = 0;
  95.         int d = dfs_list[plate_vectors[k]].second;
  96.         cout << d << "/n";
  97.         vector<int> v = plate_vectors[k];
  98.         string s = plate_words[k];
  99.         i=k;
  100.         while( v != o )
  101.         {
  102.             cout << s <<" -> ";
  103.             v = dfs_list[v].first;
  104.             i = numb[v] - 1;
  105.             s = plate_words[i];
  106.             f++;
  107.         }
  108.         if( f == dict_words[k].length() )
  109.             cout << "./n";
  110.     }
  111.  
  112.     return 0;
  113. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top