Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // by: Emiso
- #include <bits/stdc++.h>
- #define MAX 10007
- #define ALP 26
- using namespace std;
- typedef pair<int, int> pii;
- typedef long long ll;
- int C(char c) { return c - 'A'; }
- struct aho {
- int parent[MAX], suffix[MAX], to[MAX][ALP], super[MAX];
- char from[MAX];
- int id[MAX], cnt, built;
- long long ending[MAX], lazy[MAX];
- int new_node(int _parent = 0, char _from = ' ') {
- parent[cnt] = _parent; from[cnt] = _from; id[cnt] = -1;
- suffix[cnt] = super[cnt] = ending[cnt] = lazy[cnt] = 0;
- for(int i = 0; i < ALP; i++) to[cnt][i] = 0;
- return cnt++;
- }
- aho() {
- cnt = built = 0;
- new_node();
- }
- int add(string &word, int _id = 0) {
- int node = 0;
- for(int i = 0; i < word.size(); i++) {
- int nxt = C(word[i]);
- if(!to[node][nxt]) to[node][nxt] = new_node(node, word[i]);
- node = to[node][nxt];
- }
- ending[node] |= _id;
- if(id[node] == -1) id[node] = _id;
- return id[node];
- }
- void build() {
- built = 1;
- queue<int> q;
- for(int i = 0; i < ALP; i++)
- if(to[0][i]) q.push(to[0][i]);
- while(!q.empty()) {
- int v = q.front(); q.pop();
- if(parent[v]) suffix[v] = to[suffix[parent[v]]][C(from[v])];
- if(id[v] != -1) super[v] = v;
- else super[v] = super[suffix[v]];
- ending[v] |= ending[suffix[v]];
- for(int i = 0; i < ALP; i++) {
- if(!to[v][i]) to[v][i] = to[suffix[v]][i];
- else q.push(to[v][i]);
- }
- }
- }
- } dict;
- char st[57];
- int n;
- pii p[MAX][1 << 12];
- int vis[MAX][1 << 12];
- void print(pii a){
- string ans = "";
- while(a.first != 0) { ans += dict.from[a.first]; a = p[a.first][a.second]; }
- reverse(ans.begin(), ans.end());
- printf("%s\n", ans.c_str());
- }
- void bfs(){
- queue<pii> q;
- q.push({0, 0});
- vis[0][0] = 1;
- pii actual;
- while(!q.empty()){
- actual = q.front();
- q.pop();
- if(actual.second == (1 << n)-1) { print(actual); return; }
- for(int i = 0; i < 26; i++){
- int prox = dict.to[actual.first][i];
- int bit = (actual.second | dict.ending[prox]);
- if(vis[prox][bit]) continue;
- vis[prox][bit] = 1;
- p[prox][bit] = actual;
- q.push({prox, bit});
- }
- }
- }
- int main() {
- scanf("%d", &n);
- for(int i = 0; i < n; i++) {
- scanf(" %s", st);
- string s(st);
- dict.add(s, 1 << i);
- }
- dict.build();
- bfs();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement