Advertisement
Manioc

contain_us_all

Sep 21st, 2019
224
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.65 KB | None | 0 0
  1. // by: Emiso
  2. #include <bits/stdc++.h>
  3. #define MAX 10007
  4. #define ALP 26
  5.  
  6. using namespace std;
  7. typedef pair<int, int> pii;
  8. typedef long long ll;
  9. int C(char c) { return c - 'A'; }
  10.  
  11. struct aho {
  12.     int parent[MAX], suffix[MAX], to[MAX][ALP], super[MAX];
  13.     char from[MAX];
  14.     int id[MAX], cnt, built;
  15.     long long ending[MAX], lazy[MAX];
  16.  
  17.     int new_node(int _parent = 0, char _from = ' ') {
  18.         parent[cnt] = _parent; from[cnt] = _from; id[cnt] = -1;
  19.         suffix[cnt] = super[cnt] = ending[cnt] = lazy[cnt] = 0;
  20.         for(int i = 0; i < ALP; i++) to[cnt][i] = 0;
  21.         return cnt++;
  22.     }
  23.  
  24.     aho() {
  25.         cnt = built = 0;
  26.         new_node();
  27.     }
  28.  
  29.     int add(string &word, int _id = 0) {
  30.         int node = 0;
  31.         for(int i = 0; i < word.size(); i++) {
  32.             int nxt = C(word[i]);
  33.             if(!to[node][nxt]) to[node][nxt] = new_node(node, word[i]);
  34.             node = to[node][nxt];
  35.         }
  36.         ending[node] |= _id;
  37.         if(id[node] == -1) id[node] = _id;
  38.         return id[node];
  39.     }
  40.  
  41.     void build() {
  42.         built = 1;
  43.         queue<int> q;
  44.         for(int i = 0; i < ALP; i++)
  45.             if(to[0][i]) q.push(to[0][i]);
  46.  
  47.         while(!q.empty()) {
  48.             int v = q.front(); q.pop();
  49.             if(parent[v]) suffix[v] = to[suffix[parent[v]]][C(from[v])];
  50.  
  51.             if(id[v] != -1) super[v] = v;
  52.             else super[v] = super[suffix[v]];
  53.  
  54.             ending[v] |= ending[suffix[v]];
  55.             for(int i = 0; i < ALP; i++) {
  56.                 if(!to[v][i]) to[v][i] = to[suffix[v]][i];
  57.                 else q.push(to[v][i]);
  58.             }
  59.         }
  60.     }
  61.  
  62. } dict;
  63.  
  64. char st[57];
  65. int n;
  66. pii p[MAX][1 << 12];
  67. int vis[MAX][1 << 12];
  68.  
  69. void print(pii a){
  70.     string ans = "";
  71.     while(a.first != 0) { ans += dict.from[a.first]; a = p[a.first][a.second]; }
  72.     reverse(ans.begin(), ans.end());
  73.     printf("%s\n", ans.c_str());
  74. }
  75. void bfs(){
  76.     queue<pii> q;
  77.     q.push({0, 0});
  78.     vis[0][0] = 1;
  79.     pii actual;
  80.     while(!q.empty()){
  81.         actual = q.front();
  82.         q.pop();
  83.         if(actual.second == (1 << n)-1) { print(actual); return; }
  84.         for(int i = 0; i < 26; i++){
  85.             int prox = dict.to[actual.first][i];
  86.             int bit = (actual.second | dict.ending[prox]);
  87.             if(vis[prox][bit]) continue;
  88.             vis[prox][bit] = 1;
  89.             p[prox][bit] = actual;
  90.             q.push({prox, bit});
  91.         }
  92.     }
  93. }
  94. int main() {
  95.     scanf("%d", &n);
  96.  
  97.     for(int i = 0; i < n; i++) {
  98.         scanf(" %s", st);
  99.         string s(st);
  100.         dict.add(s, 1 << i);
  101.     }
  102.     dict.build();
  103.     bfs();
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement