Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #pragma comment(linker, "/STACK:16777216")
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <unordered_map>
- #include <queue>
- using namespace std;
- const int p = 239, m = 1e9 + 7;
- vector < int > pw, hs;
- struct st
- {
- int len, d, cn;
- int hs;
- st() {}
- st(int len, int d, int hs, int cn) : len(len), d(d), hs(hs), cn(cn) {}
- };
- st up(st a, int l, int nw) {
- if (a.d > 0) {
- if (l == a.d) {
- return st(a.len + a.d, 0, 0ll, a.cn + 1);
- }
- if (l < a.d) {
- return st(a.len + l, a.d - l, a.hs - nw * pw[a.d - l], a.cn + 1);
- }
- if (l > a.d) {
- return st(a.len + a.d, a.d - l, nw - a.hs * pw[l - a.d], a.cn + 1);
- }
- }
- else {
- a.d = -a.d;
- auto ans = up(a, l, nw);
- ans.d = -ans.d;
- return ans;
- }
- }
- unordered_map < int, vector < pair < int, int > > > q;
- unordered_map < int, pair < st, int > > pr;
- unordered_map < int, bool > us;
- vector < vector < int > > hsh;
- st ans(-1, 0, 0ll, 0);
- int hh(st a) {
- return a.hs * p * p + a.len * p + a.d;
- }
- bool bfs(st cur) {
- queue < st > w;
- w.push(cur);
- us[hh(cur)] = 1;
- while (!w.empty()) {
- auto now = w.front();
- w.pop();
- int h = hh(now);
- if (now.len > 20000)
- continue;
- if (!now.d && now.len && now.cn > 2) {
- ans = now;
- return 1;
- }
- for (auto i : q[now.hs]) {
- auto nx = up(now, i.second, hs[i.first]);
- int n = hh(nx);
- if (!us[n]) {
- pr[n] = { now, i.first };
- w.push(nx);
- us[n] = 1;
- }
- }
- }
- return 0;
- }
- int main() {
- iostream::sync_with_stdio(0);
- int n;
- cin >> n;
- pw.resize(101, 1);
- for (int i = 1; i < 101; i++)
- pw[i] = pw[i - 1] * p;
- hs.resize(n);
- vector < string > a(n);
- hsh.resize(n);
- for (int i = 0; i < n; i++) {
- cin >> a[i];
- hsh[i].resize(a[i].length() + 1, 0);
- for (int j = 1; j <= a[i].length(); j++)
- hsh[i][j] = hsh[i][j - 1] * p + a[i][j - 1];
- hs[i] = hsh[i][a[i].length()];
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- if (i == j)
- continue;
- for (int len = 1; len <= a[i].length(); len++) {
- int now = min(len, (int)a[j].length());
- int h = hsh[i][a[i].length()] - hsh[i][a[i].length() - len] * pw[len];
- int h1 = hsh[i][a[i].length() - (len - now)] - hsh[i][a[i].length() - len] * pw[now];
- int h2 = hsh[j][now];
- if (h1 == h2) {
- q[h].push_back({ j, a[j].length() });
- }
- }
- }
- }
- for (int i = 0; i < n; i++) {
- int h = hh(st(0, a[i].length(), hsh[i][a[i].length()], 1));
- pr[h] = { st(0, 0, 0, 0), i };
- if (bfs(st(0, a[i].length(), hsh[i][a[i].length()], 1)))
- break;
- }
- if (ans.len == -1) {
- cout << "NO\n";
- return 0;
- }
- cout << "YES\n";
- st start = st(0, 0, 0, 0);
- vector < string > ans1, ans2;
- while ((start.d != ans.d) || (start.len != ans.len) || (start.hs != ans.hs) || (start.cn != ans.cn)) {
- int h = hh(ans);
- auto p = pr[h].first;
- if (ans.d > p.d) {
- ans1.push_back(a[pr[h].second]);
- }
- else {
- ans2.push_back(a[pr[h].second]);
- }
- ans = pr[h].first;
- }
- reverse(ans1.begin(), ans1.end());
- for (string s : ans1)
- cout << s;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement