#include using namespace std; vector sort_cyclic_shifts(vector& s) { int n = s.size(); vector p(n), c(n), cnt(n); // 0th iteration: sort by first character for (int i = 0; i < n; i++) cnt[s[i]]++; for (int i = 1; i < n; i++) cnt[i] += cnt[i-1]; for (int i = 0; i < n; i++) p[--cnt[s[i]]] = i; c[p[0]] = 0; int classes = 1; for (int i = 1; i < n; i++) { if (s[p[i]] != s[p[i-1]]) classes++; c[p[i]] = classes - 1; } // remaining iterations: sort by 2^h-th cyclic shift vector pn(n), cn(n); for (int h = 0; (1 << h) < n; ++h) { for (int i = 0; i < n; i++) { pn[i] = p[i] - (1 << h); if (pn[i] < 0) pn[i] += n; } fill(cnt.begin(), cnt.begin() + classes, 0); for (int i = 0; i < n; i++) cnt[c[pn[i]]]++; for (int i = 1; i < classes; i++) cnt[i] += cnt[i-1]; for (int i = n-1; i >= 0; i--) p[--cnt[c[pn[i]]]] = pn[i]; cn[p[0]] = 0; classes = 1; for (int i = 1; i < n; i++) { pair cur = {c[p[i]], c[(p[i] + (1 << h)) % n]}; pair prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]}; if (cur != prev) ++classes; cn[p[i]] = classes - 1; } c.swap(cn); } return p; } vector lcp_construction(vector const& s, vector const& p) { int n = s.size(); vector rank(n, 0); for (int i = 0; i < n; i++) rank[p[i]] = i; int k = 0; vector lcp(n-1, 0); for (int i = 0; i < n; i++) { if (rank[i] == n - 1) { k = 0; continue; } int j = p[rank[i] + 1]; while (i + k < n && j + k < n && s[i+k] == s[j+k]) k++; lcp[rank[i]] = k; if (k) k--; } return lcp; } map token_mp; vector parse_file() { int N; string line; vector lines; while(getline(cin, line)) { if(line == "***END***") break; int hashed = 0; string stripped; int st = 0, ed = line.size(); while(st < ed && line[st] == ' ') st++; while(ed > st && line[ed-1] == ' ') ed--; for(int i=st; i st && line[i] == ' ' && line[i-1] == ' ') continue; stripped.push_back(line[i]); } if(stripped.empty()) continue; if(token_mp.count(stripped) == 0) token_mp[stripped] = token_mp.size() + 1; lines.push_back(token_mp[stripped]); } return lines; } int32_t main() { cin.tie(0)->sync_with_stdio(0); int N; cin >> N; if(N == 0) { return !(cout << "0\n"); } vector>> files; for(int i=0; i> s; files.push_back({s, parse_file()}); } vector mine = parse_file(); token_mp.clear(); vector lenacc; for(auto &[s, v]: files) { if(lenacc.empty()) { lenacc.push_back(v.size()); } else { lenacc.push_back(lenacc.back() + v.size() + 1); } } vector all; for(int i=0; i p = sort_cyclic_shifts(all); vector lcp = lcp_construction(all, p); vector best_match(files.size()); // p int cur = 0; for(int i=0; i lenacc.back()) { cur = INT_MAX; } else { if(i) cur = min(cur, lcp[i-1]); if(all[p[i]] == 0) continue; int idx = lower_bound(lenacc.begin(), lenacc.end(), p[i]) - lenacc.begin(); best_match[idx] = max(best_match[idx], cur); } } cur = 0; for(int i=p.size()-1; i>=0; i--) { if(p[i] > lenacc.back()) { cur = INT_MAX; } else { if(i < lcp.size()) cur = min(cur, lcp[i]); if(all[p[i]] == 0) continue; int idx = lower_bound(lenacc.begin(), lenacc.end(), p[i]) - lenacc.begin(); best_match[idx] = max(best_match[idx], cur); } } int ans = *max_element(best_match.begin(), best_match.end()); cout << ans << ' '; if(ans > 0) { for(int i=0; i

코드 #3583