Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- int const maxn = 4e6 + 7;
- long long const mod = 1000000007;
- map<char, int> suff[maxn];
- int link[maxn], len[maxn], k, from[maxn];
- int sz = 2, last = 1;
- string word;
- char a[200007];
- bitset<10> cnt[maxn];
- char sym[maxn];
- bool used[maxn];
- void input() {
- cin >> k;
- }
- inline void extend(char c) {
- int curr = sz++;
- sym[curr] = c;
- from[curr] = last;
- len[curr] = len[last] + 1;
- int p;
- for (p = last; p != 0 && !suff[p][c]; p = link[p]) {
- suff[p][c] = curr;
- }
- if (p == 0) {
- link[curr] = 1;
- } else {
- int q = suff[p][c];
- if (len[p] + 1 == len[q]) {
- link[curr] = q;
- } else {
- int clone = sz++;
- from[clone] = p;
- sym[clone] = sym[q];
- len[clone] = len[p] + 1;
- link[clone] = link[q];
- suff[clone] = suff[q];
- for (; p != 0 && suff[p][c] == q; p = link[p]) {
- suff[p][c] = clone;
- }
- link[q] = link[curr] = clone;
- }
- }
- last = curr;
- }
- void deep_dfs(int v) {
- if ((int) sym[v] < 97) {
- cnt[v][(int) sym[v] - 60] = true;
- return;
- }
- used[v] = true;
- for (auto it:suff[v]) {
- if (!used[it.second]) {
- deep_dfs(it.second);
- }
- cnt[v] |= cnt[it.second];
- }
- }
- void solve() {
- sym[1] = 'a';
- for (int i = 0; i < k; i++) {
- cin >> word;
- for (size_t j = 0; j < word.length(); j++) {
- extend(word[j]);
- }
- extend((char) (60 + i));
- }
- fill(used, used + maxn, false);
- deep_dfs(1);
- int ans = 0, ind = 1;
- for (int i = 2; i < sz; i++) {
- if (cnt[i].count() == k) {
- if (len[i] > ans) {
- ans = len[i];
- ind = i;
- }
- }
- }
- int pos = 0;
- for (; ind != 1; ind = from[ind]) {
- a[pos] = sym[ind];
- pos++;
- }
- for (int i = pos - 1; i >= 0; i--) {
- cout << a[i];
- }
- }
- int32_t main() {
- IOS
- input();
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement