fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define oo 1e18
  7. #define endl '\n'
  8. #define all(v) v.begin(),v.end()
  9.  
  10. #ifdef LOCAL
  11.  
  12. #include "debug.h"
  13.  
  14. #else
  15. #define dd(x...)
  16. #define ExeTime
  17. #endif
  18. int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
  19. int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};
  20.  
  21. const int N = 2e5 + 10, M = 1e2 + 10, mod = 998244353;
  22. const double EPS = 1e-12, Pi = acos(-1);
  23.  
  24. void testCase();
  25.  
  26. int main() {
  27.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  28.     int T = 1;
  29. //    cin >> T;
  30.     while (T--) testCase();
  31.     ExeTime;
  32.     return 0;
  33. }
  34.  
  35. struct SuffixArray {
  36.     string s;
  37.     vector<int> sa; // suffix array
  38.     vector<int> lcp; // longest common prefix
  39.  
  40.     SuffixArray() {};
  41.  
  42.     SuffixArray(string str) {
  43.         this->s = str;
  44.         sa = suffix_array(str);
  45.         lcp = lcp_array(str, sa);
  46.     }
  47.  
  48.     vector<int> sa_naive(const vector<int> &s) {
  49.         int n = (int) s.size();
  50.         vector<int> v(n);
  51.         iota(v.begin(), v.end(), 0);
  52.         sort(v.begin(), v.end(), [&](int l, int r) {
  53.             if (l == r) return false;
  54.             while (l < n && r < n) {
  55.                 if (s[l] != s[r]) return s[l] < s[r];
  56.                 l++;
  57.                 r++;
  58.             }
  59.             return l == n;
  60.         });
  61.         return v;
  62.     }
  63.  
  64.     vector<int> sa_doubling(const vector<int> &str) {
  65.         int n = (int) str.size();
  66.         vector<int> v(n), rnk = str, tmp(n);
  67.         iota(v.begin(), v.end(), 0);
  68.         for (int k = 1; k < n; k *= 2) {
  69.             auto cmp = [&](int x, int y) {
  70.                 if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
  71.                 int rx = x + k < n ? rnk[x + k] : -1;
  72.                 int ry = y + k < n ? rnk[y + k] : -1;
  73.                 return rx < ry;
  74.             };
  75.             sort(v.begin(), v.end(), cmp);
  76.             tmp[v[0]] = 0;
  77.             for (int i = 1; i < n; i++) {
  78.                 tmp[v[i]] = tmp[v[i - 1]] + (cmp(v[i - 1], v[i]) ? 1 : 0);
  79.             }
  80.             swap(tmp, rnk);
  81.         }
  82.         return v;
  83.     }
  84.  
  85.     template<int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>
  86.     vector<int> sa_is(const vector<int> &str, int upper) {
  87.         int n = (int) str.size();
  88.         if (n == 0) return {};
  89.         if (n == 1) return {0};
  90.         if (n == 2) {
  91.             if (str[0] < str[1]) {
  92.                 return {0, 1};
  93.             } else {
  94.                 return {1, 0};
  95.             }
  96.         }
  97.         if (n < THRESHOLD_NAIVE) {
  98.             return sa_naive(str);
  99.         }
  100.         if (n < THRESHOLD_DOUBLING) {
  101.             return sa_doubling(str);
  102.         }
  103.  
  104.         vector<int> t_sa(n);
  105.         vector<bool> ls(n);
  106.         for (int i = n - 2; i >= 0; i--) {
  107.             ls[i] = (str[i] == str[i + 1]) ? ls[i + 1] : (str[i] < str[i + 1]);
  108.         }
  109.         vector<int> sum_l(upper + 1), sum_s(upper + 1);
  110.         for (int i = 0; i < n; i++) {
  111.             if (!ls[i]) {
  112.                 sum_s[str[i]]++;
  113.             } else {
  114.                 sum_l[str[i] + 1]++;
  115.             }
  116.         }
  117.         for (int i = 0; i <= upper; i++) {
  118.             sum_s[i] += sum_l[i];
  119.             if (i < upper) sum_l[i + 1] += sum_s[i];
  120.         }
  121.  
  122.         auto induce = [&](const vector<int> &lms) {
  123.             fill(t_sa.begin(), t_sa.end(), -1);
  124.             vector<int> buf(upper + 1);
  125.             copy(sum_s.begin(), sum_s.end(), buf.begin());
  126.             for (auto d: lms) {
  127.                 if (d == n) continue;
  128.                 t_sa[buf[str[d]]++] = d;
  129.             }
  130.             copy(sum_l.begin(), sum_l.end(), buf.begin());
  131.             t_sa[buf[str[n - 1]]++] = n - 1;
  132.             for (int i = 0; i < n; i++) {
  133.                 int v = t_sa[i];
  134.                 if (v >= 1 && !ls[v - 1]) {
  135.                     t_sa[buf[str[v - 1]]++] = v - 1;
  136.                 }
  137.             }
  138.             copy(sum_l.begin(), sum_l.end(), buf.begin());
  139.             for (int i = n - 1; i >= 0; i--) {
  140.                 int v = t_sa[i];
  141.                 if (v >= 1 && ls[v - 1]) {
  142.                     t_sa[--buf[str[v - 1] + 1]] = v - 1;
  143.                 }
  144.             }
  145.         };
  146.  
  147.         vector<int> lms_map(n + 1, -1);
  148.         int m = 0;
  149.         for (int i = 1; i < n; i++) {
  150.             if (!ls[i - 1] && ls[i]) {
  151.                 lms_map[i] = m++;
  152.             }
  153.         }
  154.         vector<int> lms;
  155.         lms.reserve(m);
  156.         for (int i = 1; i < n; i++) {
  157.             if (!ls[i - 1] && ls[i]) {
  158.                 lms.push_back(i);
  159.             }
  160.         }
  161.  
  162.         induce(lms);
  163.  
  164.         if (m) {
  165.             vector<int> sorted_lms;
  166.             sorted_lms.reserve(m);
  167.             for (int v: t_sa) {
  168.                 if (lms_map[v] != -1) sorted_lms.push_back(v);
  169.             }
  170.             vector<int> rec_s(m);
  171.             int rec_upper = 0;
  172.             rec_s[lms_map[sorted_lms[0]]] = 0;
  173.             for (int i = 1; i < m; i++) {
  174.                 int l = sorted_lms[i - 1], r = sorted_lms[i];
  175.                 int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
  176.                 int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
  177.                 bool same = true;
  178.                 if (end_l - l != end_r - r) {
  179.                     same = false;
  180.                 } else {
  181.                     while (l < end_l) {
  182.                         if (str[l] != str[r]) {
  183.                             break;
  184.                         }
  185.                         l++;
  186.                         r++;
  187.                     }
  188.                     if (l == n || str[l] != str[r]) same = false;
  189.                 }
  190.                 if (!same) rec_upper++;
  191.                 rec_s[lms_map[sorted_lms[i]]] = rec_upper;
  192.             }
  193.  
  194.             auto rec_sa =
  195.                     sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);
  196.  
  197.             for (int i = 0; i < m; i++) {
  198.                 sorted_lms[i] = lms[rec_sa[i]];
  199.             }
  200.             induce(sorted_lms);
  201.         }
  202.         return t_sa;
  203.     }
  204.  
  205.  
  206.     vector<int> suffix_array(const vector<int> &str, int upper) {
  207.         assert(0 <= upper);
  208.         for (int d: str) {
  209.             assert(0 <= d && d <= upper);
  210.         }
  211.         return sa_is(str, upper);
  212.     }
  213.  
  214.     template<class T>
  215.     vector<int> suffix_array(const vector<T> &str) {
  216.         int n = int(str.size());
  217.         vector<int> idx(n);
  218.         iota(idx.begin(), idx.end(), 0);
  219.         sort(idx.begin(), idx.end(), [&](int l, int r) { return str[l] < str[r]; });
  220.         vector<int> s2(n);
  221.         int now = 0;
  222.         for (int i = 0; i < n; i++) {
  223.             if (i && str[idx[i - 1]] != str[idx[i]]) now++;
  224.             s2[idx[i]] = now;
  225.         }
  226.         return sa_is(s2, now);
  227.     }
  228.  
  229.     vector<int> suffix_array(const string &str) {
  230.         int n = int(str.size());
  231.         vector<int> s2(n);
  232.         for (int i = 0; i < n; i++) {
  233.             s2[i] = str[i];
  234.         }
  235.         return sa_is(s2, 255);
  236.     }
  237.  
  238.     template<class T>
  239.     vector<int> lcp_array(const vector<T> &str, const vector<int> &s_a) {
  240.         int n = int(str.size());
  241.         assert(n >= 1);
  242.         vector<int> rnk(n);
  243.         for (int i = 0; i < n; i++) {
  244.             rnk[s_a[i]] = i;
  245.         }
  246.         vector<int> v(n - 1);
  247.         int h = 0;
  248.         for (int i = 0; i < n; i++) {
  249.             if (h > 0) h--;
  250.             if (rnk[i] == 0) continue;
  251.             int j = s_a[rnk[i] - 1];
  252.             for (; j + h < n && i + h < n; h++) {
  253.                 if (str[j + h] != str[i + h]) break;
  254.             }
  255.             v[rnk[i] - 1] = h;
  256.         }
  257.         return v;
  258.     }
  259.  
  260.     vector<int> lcp_array(const string &str, const vector<int> &s_a) {
  261.         int n = int(str.size());
  262.         vector<int> s2(n);
  263.         for (int i = 0; i < n; i++) {
  264.             s2[i] = str[i];
  265.         }
  266.         return lcp_array(s2, s_a);
  267.     }
  268.  
  269.     bool check(int mid, const string &t, bool greater = true) {
  270.         int i = 0, j = sa[mid], m = (int) t.size();
  271.         while (i < m && j < s.size()) {
  272.             if (t[i] > s[j]) return false;
  273.             if (t[i++] < s[j++]) return true;
  274.         }
  275.         return greater;
  276.     }
  277.  
  278.     int lower_bound(const string &t) { // O(min(n,m)*log(n))
  279.         int l = 0, r = s.size() - 1, ans = s.size(), mid;
  280.         while (l <= r) {
  281.             mid = (l + r) >> 1;
  282.             if (check(mid, t)) r = mid - 1, ans = mid;
  283.             else l = mid + 1;
  284.         }
  285.         return ans;
  286.     }
  287.  
  288.     int upper_bound(const string &t) { // O(min(n,t,size())*log(n))
  289.         int l = 0, r = s.size() - 1, ans = s.size(), mid;
  290.         while (l <= r) {
  291.             mid = (l + r) >> 1;
  292.             if (check(mid, t, 0)) r = mid - 1, ans = mid;
  293.             else l = mid + 1;
  294.         }
  295.         return ans;
  296.     }
  297.  
  298.     bool exists_as_substr(const string t) {
  299.         return occurrence_as_substr(t);
  300.     }
  301.  
  302.     int occurrence_as_substr(const string &t) {
  303.         return upper_bound(t) - lower_bound(t);
  304.     }
  305. };
  306.  
  307. template<typename T>
  308. struct sliding_window {
  309.     deque<pair<T, int>> d;
  310.     int l, r;
  311.  
  312.     sliding_window() : l(0), r(0) {}
  313.  
  314.     void push_back(T x) {
  315.         while (!d.empty() && d.back().first >= x) d.pop_back();
  316.         d.emplace_back(x, r++);
  317.     }
  318.  
  319.     void pop_front() {
  320.         if (d.front().second == l++) d.pop_front();
  321.     }
  322.  
  323.     T get_min() {
  324.         return d.front().first;
  325.     }
  326. };
  327.  
  328. int lcs(vector<string> s, int k = -1) { // longest common substring
  329.     if (k == -1) k = s.size();
  330.     if (k == 1) {
  331.         int ind = max_element(all(s), [](string &a, string &b) {
  332.             return a.size() < b.size();
  333.         }) - s.begin();
  334.         int mx = s[ind].size();
  335.         return mx;
  336.     }
  337.     string concat = s[0];
  338.     char ch = char(0); // note !! number of string should not be more than 35
  339.     for (int i = 1; i < s.size(); i++) concat += (ch++) + s[i];
  340.     SuffixArray sa(concat);
  341.     int n = concat.size();
  342.     vector<int> group(n, 1);
  343.     for (int i = 1, j = 0, sum = s[0].size() + 1; i < n; i++) {
  344.         group[i] = group[i - 1];
  345.         if (i == sum) {
  346.             group[i]++;
  347.             sum += s[++j].size() + 1;
  348.         }
  349.     }
  350.     int cnt = 0;
  351.     vector<int> mp(n + 1);
  352.     sliding_window<pair<int, int>> sw;
  353.     pair<int, int> mx = {0, 0};
  354.     for (int i = 0, j = 0; j < n; i++) {
  355.         while (cnt < k && j < n) {
  356.             cnt += (mp[group[sa.sa[j]]]++ == 0);
  357.             if (j) sw.push_back({sa.lcp[j - 1], sa.sa[j]});
  358.             j++;
  359.         }
  360.         auto mn = sw.get_min();
  361.         if (cnt == k && mn.first >= mx.first) {
  362.             mx = max(mx, mn);
  363.         }
  364.         sw.pop_front();
  365.         cnt -= (--mp[group[sa.sa[i]]] == 0);
  366.     }
  367.     return mx.first;
  368. }
  369.  
  370. void testCase() {
  371.  
  372.     string s;
  373.     vector<string> a;
  374.     while (cin >> s) a.push_back(s);
  375.     cout << lcs(a) << endl;
  376. }
  377.  
Success #stdin #stdout 0.01s 5436KB
comments (?)
stdin
copy 
alsdfkjfjkdsal
fdjskalajfkdsla
aaaajfaaaa
stdout
copy 
2
https://ideone.com/WKmyjD
problem LCS2, based on SPOJ submission 31811082 (CPP14), 2023-09-08 11:28:43
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!