#include #define all(v) v.begin(), v.end() #define prs(v) sort(all(v)); v.erase(unique(all(v)), v.end()) using namespace std; using ll = long long; using P = pair; pair, vector> SuffixArray(const string &s){ int n = s.size(), m = max(n, 256); vector sa(n), lcp(n), pos(n), tmp(n), cnt(m); auto counting_sort = [&](){ fill(cnt.begin(), cnt.end(), 0); for(int i=0; i=0; i--) sa[--cnt[pos[tmp[i]]]] = tmp[i]; }; for(int i=0; i= k) tmp[p++] = sa[i] - k; counting_sort(); tmp[sa[0]] = 0; for(int i=1; i struct RMQ { int n, lg; vector> v; RMQ() = default; RMQ(const vector &a) : n(a.size()), lg(__lg(n)), v(lg+1, vector(n)) { copy(a.begin(), a.end(), v[0].begin()); for(int i=1; i<=lg; i++) for(int j=0; j+(1<sync_with_stdio(0); int n; cin >> n; string T; vector A(n); for (auto &s : A) cin >> s, T += s + '#'; if (n == 1) { cout << A[0] << "\n"; return 0; } auto [sa, lcp] = SuffixArray(T); vector pos(sa.size()); for (int s = 0; s < T.size(); s++) pos[sa[s]] = s; vector I(T.size()); for (int s = 0, e = 0; s < n; s++) { int x = e; for (; x < e + A[s].size(); x++) I[x] = s; I[x] = n + 1; e = ++x; } RMQ rmq(lcp); vector S(T.size() + 1, vector(n, 0)); for (int s = 0; s < T.size(); s++) { if (s) S[s] = S[s - 1]; int i = I[sa[s]]; if (i <= n) S[s][i]++; } string ans; int i = -1; for (int s = 0; s < T.size(); s++) { int now = lcp[s]; int L, R; int l = -1, r = s; while (l + 1 < r) { int m = (l + r) >> 1; (rmq.query(m, s) >= now ? r : l) = m; } L = l = r; r = T.size(); while (l + 1 < r) { int m = (l + r) >> 1; assert (m < T.size()); (rmq.query(L, m) >= now ? l : r) = m; } R = l; int op = now > 0; for (int e = 0; e < n; e++) { if (S[R][e] == (L - 2 >= 0 ? S[L - 2][e] : 0)) op = 0; } if (op) { string now_str = T.substr(sa[s], now); if (now_str.back() == '#') now_str.pop_back(); if (ans.size() < now_str.size() || (ans.size() == now_str.size() && i > sa[s])) ans = now_str, i = sa[s]; } } cout << ans << "\n"; }

제출 #144362

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: