Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- #include <vector>
- using namespace std;
- map <vector <int>, pair <vector <int>, int>> dfs_list;
- map <vector <int>, int> numb;
- vector <int> o(26);
- pair <vector<int>, int> o1(o, 1);
- pair <vector <int>, int> dfs( vector <int> a )
- {
- if( dfs_list[a].second )
- return dfs_list[a];
- else
- {
- int s = 0;
- int i;
- for( i = 0; i < 26; i++ )
- s+=a[i];
- if( s == 1 )
- dfs_list[a] = o1;
- else
- {
- s = 0;
- vector <int> u(26);
- map <int, vector <int>> mas;
- for( i = 0; i < 26; i++ )
- if( a[i] )
- {
- u = a;
- u[i]--;
- if( numb[u] )
- {
- mas[s] = u;
- s++;
- }
- }
- if( !s )
- dfs_list[a] = o1;
- else
- {
- int k = 0;
- int ways[s];
- for( i = 0; i < s; i++ )
- ways[i] = dfs( mas[i] ).second;
- int l = ways[0];
- for( i = 1; i < s; i++ )
- if( ways[i] > l )
- {
- l = ways[i];
- k = i;
- }
- dfs_list[a] = make_pair(mas[k], ways[k]+1);
- }
- }
- return dfs_list[a];
- }
- }
- int main()
- {
- cin.tie(0);
- ios_base::sync_with_stdio(0);
- int n;
- cin >> n;
- vector<string> plate_words(n);
- vector<vector<int>> plate_vectors(n);
- int k;
- int i;
- for( k = 0; k < n; k++ )
- {
- cin >> plate_words[k];
- plate_vectors[k].resize(26);
- for( i = 0; i < plate_words[k].length(); i++ )
- plate_vectors[k][plate_words[k][i]-'a']++;
- }
- int m;
- cin >> m;
- vector<string> dict_words(m);
- vector<vector<int>> dict_vectors(m);
- for( k = 0; k < m; k++ )
- {
- cin >> dict_words[k];
- dict_vectors[k].resize(26);
- for( i = 0; i < dict_words[k].length(); i++ )
- dict_vectors[k][dict_words[k][i]-'a']++;
- numb[dict_vectors[k]] = k + 1;
- }
- for( k = 0; k < n; k++ )
- {
- int f = 0;
- int d = dfs_list[plate_vectors[k]].second;
- cout << d << "/n";
- vector<int> v = plate_vectors[k];
- string s = plate_words[k];
- i=k;
- while( v != o )
- {
- cout << s <<" -> ";
- v = dfs_list[v].first;
- i = numb[v] - 1;
- s = plate_words[i];
- f++;
- }
- if( f == dict_words[k].length() )
- cout << "./n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement