Advertisement
Josif_tepe

Untitled

Feb 8th, 2024
709
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.49 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <cstring>
  5. using namespace std;
  6. typedef long long ll;
  7. const int maxn = 205;
  8. const int alphabet_size = 26;
  9. map<int, int> at_trie_is_end_of_word;
  10. int trie[maxn][alphabet_size];
  11. ll dp[28][1 << 9][maxn];
  12. int o, n;
  13. ll rec(int at, int visited, int at_trie) {
  14.     if(at == o and __builtin_popcount(visited) == n) {
  15.         return 1;
  16.     }
  17.     if(at >= o) {
  18.         return 0;
  19.     }
  20.     if(dp[at][visited][at_trie] != -1) {
  21.         return dp[at][visited][at_trie];
  22.     }
  23.     ll res = 0;
  24.     for(char c = 'a'; c <= 'z'; c++) {
  25.         int id = trie[at_trie][c - 'a'];
  26.         res += rec(at + 1, (visited | at_trie_is_end_of_word[id]), id);
  27.     }
  28.     return dp[at][visited][at_trie] = res;
  29. }
  30. void generate_strings(int at, int visited, int at_trie, string tmp) {
  31.     if(at == o and __builtin_popcount(visited) == n) {
  32.         cout << tmp << endl;
  33.         return;
  34.     }
  35.     if(at >= o) {
  36.         return;
  37.     }
  38.     for(char c = 'a'; c <= 'z'; c++) {
  39.         int id = trie[at_trie][c - 'a'];
  40.         if(rec(at + 1, visited | at_trie_is_end_of_word[id], id) > 0) {
  41.             generate_strings(at + 1, visited | at_trie_is_end_of_word[id], id, tmp + c);
  42.         }
  43.     }
  44. }
  45. int main() {
  46.     ios_base::sync_with_stdio(false);
  47.     cin >> o >> n;
  48.     memset(dp, -1, sizeof dp);
  49.     vector<string> v(n);
  50.     for(int i = 0; i < n; i++) {
  51.         cin >> v[i];
  52.     }
  53.     int idx = 1;
  54.     map<string, int> m1;
  55.     map<int, string> m2;
  56.     for(int i = 0; i < n; i++) {
  57.         string tmp = "";
  58.         for(int j = 0; j < (int) v[i].size(); j++) {
  59.             tmp += v[i][j];
  60.             m1[tmp] = idx;
  61.             m2[idx] = tmp;
  62.             idx++;
  63.            
  64.         }
  65.     }
  66.     m1[""] = 0;
  67.     m2[0] = "";
  68.     for(int i = 0; i <= 100; i++) {
  69.         if(m2.find(i) != m2.end()) {
  70.             for(int j = 0; j < n; j++) {
  71.                 if((int) m2[i].size() >= (int) v[j].size() and m2[i].find(v[j]) != string::npos) {
  72.                     at_trie_is_end_of_word[i] |= (1 << j);
  73.                 }
  74.             }
  75.         }
  76.         string tmp = "";
  77.         for(char c = 'a'; c <= 'z'; c++) {
  78.             tmp = m2[i] + c;
  79.             while(m1.find(tmp) == m1.end()) {
  80.                 tmp.erase(tmp.begin());
  81.             }
  82.             trie[i][c - 'a'] = m1[tmp];
  83.         }
  84.        
  85.     }
  86.    
  87.     ll res = rec(0, 0, 0);
  88.     cout << res << endl;
  89.     if(res < 30) {
  90.         generate_strings(0, 0, 0, "");
  91.     }
  92.     return 0;
  93. }
  94.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement