fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. // =============================================================================
  7. // Suffix Array & LCP (Longest Common Prefix) – Collection of Algorithms
  8. // =============================================================================
  9. //
  10. // This file contains a set of functions that work with Suffix Arrays and
  11. // LCP arrays. Each function is explained with:
  12. //   - What it does (Purpose)
  13. //   - What it expects (Input)
  14. //   - What it returns (Output)
  15. //   - Time complexity
  16. //   - Important notes and constraints
  17. //
  18. // TERMINOLOGY (in simple words):
  19. //   - Suffix: a substring that starts at some position and goes to the end.
  20. //   - Suffix Array (SA): the starting positions of all suffixes, sorted
  21. //     lexicographically (dictionary order).
  22. //   - Rank: the position (index) of a suffix inside the Suffix Array.
  23. //   - LCP: Longest Common Prefix between two strings (or suffixes).
  24. //   - LCP Array: `lcp[i]` = LCP of the suffixes at SA[i] and SA[i+1].
  25. //   - RMQ: Range Minimum Query – quickly find the minimum value in a range.
  26. //   - Sparse Table: a data structure that answers RMQ in O(1) after
  27. //     O(n log n) preprocessing.
  28. //   - Sentinel: a special unique character (here '$') added to the end of
  29. //     the string to make suffix sorting easier. It is smaller than all
  30. //     normal characters.
  31. //   - Separator: a unique character used when joining several strings into
  32. //     one; it must not appear in the original strings.
  33. // =============================================================================
  34.  
  35.  
  36. // =============================================================================
  37. // 1) BUILD SUFFIX ARRAY – O(n log n)
  38. // =============================================================================
  39.  
  40. /**
  41.  * Purpose:
  42.  *   Builds the suffix array of a given string.
  43.  *
  44.  * Input:
  45.  *   s : the input string (can contain any printable ASCII characters except '$').
  46.  *       A sentinel '$' is added automatically – do NOT include it yourself.
  47.  * Output:
  48.  *   A vector<int> containing the starting positions (0‑based) of all suffixes,
  49.  *   sorted in lexicographical order. The sentinel's position is removed.
  50.  * Time Complexity:
  51.  *   O(n log n) where n = s.length().
  52.  * Constraints:
  53.  *   - The character '$' must NOT appear in s.
  54.  *   - Works comfortably for strings up to ~2·10^5.
  55.  * Notes:
  56.  *   - The algorithm uses a standard counting‑sort / radix‑sort approach.
  57.  *   - The returned SA size equals the length of the original string.
  58.  */
  59. vector<int> buildSuffixArray(const string& s) {
  60.     string str = s;
  61.     str.push_back('$');                // sentinel (smaller than any other char)
  62.     int n = (int)str.size();
  63.     vector<int> p(n), c(n);
  64.  
  65.     // k = 0 : sort single characters
  66.     vector<pair<char,int>> a(n);
  67.     for (int i = 0; i < n; i++) a[i] = {str[i], i};
  68.     sort(a.begin(), a.end());
  69.     for (int i = 0; i < n; i++) p[i] = a[i].second;
  70.     c[p[0]] = 0;
  71.     for (int i = 1; i < n; i++) {
  72.         c[p[i]] = c[p[i-1]] + (a[i].first != a[i-1].first);
  73.     }
  74.  
  75.     // transitions
  76.     vector<int> pn(n), cn(n);
  77.     for (int h = 0; (1 << h) < n; h++) {
  78.         for (int i = 0; i < n; i++) {
  79.             pn[i] = p[i] - (1 << h);
  80.             if (pn[i] < 0) pn[i] += n;
  81.         }
  82.         vector<int> cnt(n, 0);
  83.         for (int i = 0; i < n; i++) cnt[c[pn[i]]]++;
  84.         vector<int> pos(n);
  85.         pos[0] = 0;
  86.         for (int i = 1; i < n; i++) pos[i] = pos[i-1] + cnt[i-1];
  87.         for (int i = 0; i < n; i++) {
  88.             int cl = c[pn[i]];
  89.             p[pos[cl]++] = pn[i];
  90.         }
  91.         cn[p[0]] = 0;
  92.         for (int i = 1; i < n; i++) {
  93.             pair<int,int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
  94.             pair<int,int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
  95.             cn[p[i]] = cn[p[i-1]] + (cur != prev);
  96.         }
  97.         c.swap(cn);
  98.     }
  99.  
  100.     // remove the sentinel position (it is always the last index n-1 after sorting)
  101.     vector<int> sa;
  102.     sa.reserve(n-1);
  103.     for (int x : p) if (x != n-1) sa.push_back(x);
  104.     return sa;
  105. }
  106.  
  107.  
  108. // =============================================================================
  109. // 2) BUILD LCP ARRAY – O(n) (Kasai's algorithm)
  110. // =============================================================================
  111.  
  112. /**
  113.  * Purpose:
  114.  *   Builds the LCP array from the original string and its suffix array.
  115.  *   lcp[i] = LCP of suffixes sa[i] and sa[i+1].
  116.  *
  117.  * Input:
  118.  *   s  : the original string (without sentinel)
  119.  *   sa : suffix array of s (from buildSuffixArray)
  120.  * Output:
  121.  *   A vector<int> of size n-1 (empty if n <= 1).
  122.  * Time Complexity:
  123.  *   O(n)
  124.  * Constraints:
  125.  *   sa must be a valid suffix array of s.
  126.  */
  127. vector<int> buildLCP(const string& s, const vector<int>& sa) {
  128.     int n = (int)s.size();
  129.     vector<int> rank(n, 0);
  130.     for (int i = 0; i < n; i++) rank[sa[i]] = i;
  131.     vector<int> lcp(max(0, n-1), 0);
  132.     int k = 0;
  133.     for (int i = 0; i < n; i++) {
  134.         if (rank[i] == n-1) { k = 0; continue; }
  135.         int j = sa[rank[i] + 1];
  136.         while (i + k < n && j + k < n && s[i+k] == s[j+k]) k++;
  137.         lcp[rank[i]] = k;
  138.         if (k) k--;
  139.     }
  140.     return lcp;
  141. }
  142.  
  143.  
  144. // =============================================================================
  145. // 3) SPARSE TABLE FOR RMQ ON LCP
  146. // =============================================================================
  147.  
  148. /**
  149.  * Purpose:
  150.  *   Preprocesses the LCP array to answer Range Minimum Queries (RMQ) in O(1).
  151.  *   This allows fast LCP queries between any two suffixes.
  152.  *
  153.  * Input:
  154.  *   lcp : the LCP array (size n-1; may be empty if n <= 1).
  155.  * Output:
  156.  *   An object that can answer min(lcp[l..r]) in O(1).
  157.  * Time Complexity:
  158.  *   Preprocessing: O(m log m) where m = lcp.size().
  159.  *   Query: O(1).
  160.  */
  161. class LCPRMQ {
  162. private:
  163.     vector<int> lg;
  164.     vector<vector<int>> st;
  165. public:
  166.     LCPRMQ(const vector<int>& lcp) {
  167.         int m = (int)lcp.size();
  168.         lg.assign(m + 1, 0);
  169.         for (int i = 2; i <= m; i++) lg[i] = lg[i/2] + 1;
  170.         if (m == 0) return;
  171.         st.assign(m, vector<int>(lg[m] + 1));
  172.         for (int i = 0; i < m; i++) st[i][0] = lcp[i];
  173.         for (int k = 1; (1 << k) <= m; k++) {
  174.             for (int i = 0; i + (1 << k) <= m; i++) {
  175.                 st[i][k] = min(st[i][k-1], st[i + (1 << (k-1))][k-1]);
  176.             }
  177.         }
  178.     }
  179.  
  180.     /**
  181.      * Query the minimum LCP in the range [l, r] inclusive.
  182.      * Requires 0 <= l <= r < lcp.size().
  183.      */
  184.     int query(int l, int r) const {
  185.         if (l > r) return INT_MAX;   // empty range
  186.         int len = r - l + 1;
  187.         int k = lg[len];
  188.         return min(st[l][k], st[r - (1 << k) + 1][k]);
  189.     }
  190. };
  191.  
  192.  
  193. // =============================================================================
  194. // 4) LCP BETWEEN ANY TWO POSITIONS – O(1)
  195. // =============================================================================
  196.  
  197. /**
  198.  * Purpose:
  199.  *   Computes the LCP of the two suffixes starting at positions i and j
  200.  *   in the original string.
  201.  *
  202.  * Input:
  203.  *   s    : the original string
  204.  *   sa   : suffix array of s
  205.  *   rank : rank array (rank[pos] = index in SA)
  206.  *   rmq  : LCPRMQ object built from the LCP array
  207.  *   i, j : starting positions (0‑based) in the string
  208.  * Output:
  209.  *   Length of the longest common prefix of s[i..] and s[j..].
  210.  * Time Complexity:
  211.  *   O(1)
  212.  * Notes:
  213.  *   If i == j, the whole remaining length is returned.
  214.  */
  215. int lcpBetweenPositions(const string& s, const vector<int>& sa,
  216.                         const vector<int>& rank, const LCPRMQ& rmq,
  217.                         int i, int j) {
  218.     int n = (int)s.size();
  219.     if (i == j) return n - i;
  220.     int l = rank[i], r = rank[j];
  221.     if (l > r) swap(l, r);
  222.     // LCP of SA[l] and SA[r] is the minimum in lcp[l .. r-1]
  223.     return rmq.query(l, r-1);
  224. }
  225.  
  226.  
  227. // =============================================================================
  228. // 5) PATTERN SEARCH (count / find occurrences)
  229. // =============================================================================
  230.  
  231. /**
  232.  * Purpose:
  233.  *   Count how many times a pattern occurs as a substring in the text.
  234.  *
  235.  * Input:
  236.  *   s       : the text
  237.  *   sa      : suffix array of s
  238.  *   pattern : the pattern to search for
  239.  * Output:
  240.  *   Number of starting positions where pattern appears.
  241.  * Time Complexity:
  242.  *   O(|pattern| * log n) using two binary searches.
  243.  * Notes:
  244.  *   If the pattern is empty, it returns n+1 (all positions + empty suffix).
  245.  */
  246. int countOccurrences(const string& s, const vector<int>& sa, const string& pattern) {
  247.     int n = (int)s.size();
  248.     int m = (int)pattern.size();
  249.     if (m == 0) return n + 1;
  250.  
  251.     // compare a suffix starting at 'pos' with the pattern
  252.     auto suffixCmp = [&](int pos, const string& pat) -> int {
  253.         int len = min((int)pat.size(), n - pos);
  254.         int cmp = s.compare(pos, len, pat, 0, len);
  255.         if (cmp != 0) return cmp;
  256.         if (len == (int)pat.size()) return 0;       // strings equal up to pat length
  257.         return (n - pos < (int)pat.size()) ? -1 : 1; // shorter suffix < pattern
  258.     };
  259.  
  260.     // lower bound: first index where suffix >= pattern
  261.     int lo = 0, hi = n;
  262.     while (lo < hi) {
  263.         int mid = (lo + hi) / 2;
  264.         if (suffixCmp(sa[mid], pattern) < 0)
  265.             lo = mid + 1;
  266.         else
  267.             hi = mid;
  268.     }
  269.     int first = lo;
  270.  
  271.     // upper bound: first index where suffix > pattern
  272.     lo = 0; hi = n;
  273.     while (lo < hi) {
  274.         int mid = (lo + hi) / 2;
  275.         if (suffixCmp(sa[mid], pattern) <= 0)
  276.             lo = mid + 1;
  277.         else
  278.             hi = mid;
  279.     }
  280.     int last = lo;
  281.  
  282.     return last - first;
  283. }
  284.  
  285. /**
  286.  * Purpose:
  287.  *   Returns all starting positions where the pattern occurs in the text.
  288.  *
  289.  * Input:
  290.  *   s, sa, pattern : same as countOccurrences
  291.  * Output:
  292.  *   A vector<int> of starting indices (0‑based). Sorted ascending.
  293.  * Time Complexity:
  294.  *   O(|pattern| * log n + occ), occ = number of occurrences.
  295.  */
  296. vector<int> findOccurrences(const string& s, const vector<int>& sa, const string& pattern) {
  297.     int n = (int)s.size();
  298.     int m = (int)pattern.size();
  299.     vector<int> res;
  300.     if (m == 0) {
  301.         for (int i = 0; i <= n; i++) res.push_back(i);
  302.         return res;
  303.     }
  304.  
  305.     auto suffixCmp = [&](int pos, const string& pat) -> int {
  306.         int len = min((int)pat.size(), n - pos);
  307.         int cmp = s.compare(pos, len, pat, 0, len);
  308.         if (cmp != 0) return cmp;
  309.         if (len == (int)pat.size()) return 0;
  310.         return (n - pos < (int)pat.size()) ? -1 : 1;
  311.     };
  312.  
  313.     int lo = 0, hi = n;
  314.     while (lo < hi) {
  315.         int mid = (lo + hi) / 2;
  316.         if (suffixCmp(sa[mid], pattern) < 0)
  317.             lo = mid + 1;
  318.         else
  319.             hi = mid;
  320.     }
  321.     int first = lo;
  322.  
  323.     lo = 0; hi = n;
  324.     while (lo < hi) {
  325.         int mid = (lo + hi) / 2;
  326.         if (suffixCmp(sa[mid], pattern) <= 0)
  327.             lo = mid + 1;
  328.         else
  329.             hi = mid;
  330.     }
  331.     int last = lo;
  332.  
  333.     for (int i = first; i < last; i++) res.push_back(sa[i]);
  334.     return res;
  335. }
  336.  
  337.  
  338. // =============================================================================
  339. // 6) COUNT DISTINCT SUBSTRINGS
  340. // =============================================================================
  341.  
  342. /**
  343.  * Purpose:
  344.  *   Count the number of distinct non‑empty substrings of a string.
  345.  *
  346.  * Input:
  347.  *   s : the string.
  348.  * Output:
  349.  *   A 64‑bit integer: total distinct substrings.
  350.  * Time Complexity:
  351.  *   O(n log n) (SA construction) + O(n) (LCP).
  352.  * Formula:
  353.  *   Total possible substrings = n*(n+1)/2, subtract sum(LCP) because each
  354.  *   LCP value counts duplicate prefixes between adjacent suffixes.
  355.  */
  356. ll countDistinctSubstrings(const string& s) {
  357.     int n = (int)s.size();
  358.     vector<int> sa = buildSuffixArray(s);
  359.     vector<int> lcp = buildLCP(s, sa);
  360.     ll total = 1LL * n * (n + 1) / 2;
  361.     ll sumLCP = 0;
  362.     for (int x : lcp) sumLCP += x;
  363.     return total - sumLCP;
  364. }
  365.  
  366.  
  367. // =============================================================================
  368. // 7) LONGEST REPEATED SUBSTRING
  369. // =============================================================================
  370.  
  371. /**
  372.  * Purpose:
  373.  *   Find the length of the longest substring that appears at least twice
  374.  *   (overlapping allowed).
  375.  *
  376.  * Input:
  377.  *   s : the string.
  378.  * Output:
  379.  *   Length of the longest repeated substring, or 0 if none.
  380.  * Time Complexity:
  381.  *   O(n log n) (SA) + O(n) (LCP). The answer is simply max(LCP array).
  382.  * Notes:
  383.  *   To obtain the actual substring, use sa[i] and lcp[i] at the maximum index.
  384.  */
  385. int longestRepeatedSubstring(const string& s) {
  386.     int n = (int)s.size();
  387.     if (n < 2) return 0;
  388.     vector<int> sa = buildSuffixArray(s);
  389.     vector<int> lcp = buildLCP(s, sa);
  390.     int best = 0;
  391.     for (int x : lcp) best = max(best, x);
  392.     return best;
  393. }
  394.  
  395.  
  396. // =============================================================================
  397. // 8) LONGEST COMMON SUBSTRING BETWEEN TWO STRINGS
  398. // =============================================================================
  399.  
  400. /**
  401.  * Purpose:
  402.  *   Find the length of the longest substring that appears in both s1 and s2.
  403.  *
  404.  * Input:
  405.  *   s1, s2 : two strings.
  406.  * Output:
  407.  *   Length of the longest common substring (0 if none).
  408.  * Time Complexity:
  409.  *   O((n+m) log(n+m)) for SA + LCP.
  410.  * Constraints:
  411.  *   The separator character '#' must NOT appear in s1 or s2.
  412.  * Notes:
  413.  *   The two strings are concatenated as s1 + '#' + s2. The suffix array of
  414.  *   this combined string is built (with an automatic sentinel). Then we scan
  415.  *   the LCP array and consider only pairs of suffixes where one comes from s1
  416.  *   and the other from s2.
  417.  */
  418. int longestCommonSubstring(const string& s1, const string& s2) {
  419.     string comb = s1 + "#" + s2;          // sentinel will be added internally
  420.     int n1 = s1.size();
  421.     vector<int> sa = buildSuffixArray(comb);
  422.     vector<int> lcp = buildLCP(comb, sa);
  423.     int best = 0;
  424.     for (int i = 0; i < (int)lcp.size(); i++) {
  425.         int pos1 = sa[i];
  426.         int pos2 = sa[i+1];
  427.         bool in1_first  = (pos1 < n1);
  428.         bool in2_first  = (pos1 > n1);    // > because separator is at n1
  429.         bool in1_second = (pos2 < n1);
  430.         bool in2_second = (pos2 > n1);
  431.         if ((in1_first && in2_second) || (in2_first && in1_second)) {
  432.             best = max(best, lcp[i]);
  433.         }
  434.     }
  435.     return best;
  436. }
  437.  
  438.  
  439. // =============================================================================
  440. // 9) LONGEST COMMON SUBSTRING AMONG MULTIPLE STRINGS
  441. // =============================================================================
  442.  
  443. /**
  444.  * Purpose:
  445.  *   Find the length of the longest substring that appears in ALL given strings.
  446.  *
  447.  * Input:
  448.  *   strs : vector of strings.
  449.  * Output:
  450.  *   Length of the longest common substring (0 if none).
  451.  * Time Complexity:
  452.  *   O(N log N + N log L) where N = total length of all strings + separators,
  453.  *   L = maximum possible answer.
  454.  * Method:
  455.  *   1. Concatenate all strings with unique separators (characters from ASCII 1
  456.  *      upwards, which are not printable – safe because inputs are printable ASCII).
  457.  *   2. Build SA and LCP of the combined string.
  458.  *   3. Binary search on the answer length. For a given length `len`, check if
  459.  *      there exists a block of suffixes in the SA such that:
  460.  *         - every adjacent LCP inside the block is >= len,
  461.  *         - the block contains suffixes from every original string.
  462.  *
  463.  * Constraints:
  464.  *   - Strings must consist of printable ASCII characters (32‑126).
  465.  *   - k >= 1 (if k == 1 the whole string is the answer).
  466.  */
  467. int longestCommonSubstringMultiple(vector<string>& strs) {
  468.     int k = (int)strs.size();
  469.     if (k == 0) return 0;
  470.     if (k == 1) return (int)strs[0].size();
  471.  
  472.     // Build the concatenated string and an owner array for every position.
  473.     string combined;
  474.     vector<int> owner;   // owner[i] = index of the string this character belongs to,
  475.                          // -1 for separators.
  476.     for (int i = 0; i < k; i++) {
  477.         if (i > 0) {
  478.             // Use ASCII codes 1,2,3... as unique separators.
  479.             // They are guaranteed not to appear in the original strings.
  480.             combined.push_back(char(1 + i));   // separator for string i
  481.             owner.push_back(-1);
  482.         }
  483.         for (char c : strs[i]) {
  484.             combined.push_back(c);
  485.             owner.push_back(i);
  486.         }
  487.     }
  488.  
  489.     int n = combined.size();
  490.     vector<int> sa = buildSuffixArray(combined);
  491.     vector<int> lcp = buildLCP(combined, sa);
  492.  
  493.     // Map each suffix (by its SA index) to its owner.
  494.     vector<int> saOwner(n, -1);
  495.     for (int i = 0; i < n; i++) {
  496.         int pos = sa[i];
  497.         if (pos < (int)owner.size())
  498.             saOwner[i] = owner[pos];
  499.     }
  500.  
  501.     // Check if a common substring of length `len` exists.
  502.     auto check = [&](int len) -> bool {
  503.         vector<int> cnt(k, 0);
  504.         int distinct = 0;
  505.         for (int i = 0; i < n; i++) {
  506.             int own = saOwner[i];
  507.             if (own != -1) {
  508.                 if (cnt[own] == 0) distinct++;
  509.                 cnt[own]++;
  510.             }
  511.  
  512.             // End of a block when we are at the last suffix or the LCP to the
  513.             // next suffix is smaller than `len`.
  514.             if (i == n-1 || lcp[i] < len) {
  515.                 if (distinct == k) return true;
  516.                 // reset for next block
  517.                 fill(cnt.begin(), cnt.end(), 0);
  518.                 distinct = 0;
  519.             }
  520.         }
  521.         return false;
  522.     };
  523.  
  524.     // Binary search for the maximum possible length.
  525.     int lo = 0, hi = n + 1;
  526.     while (lo < hi) {
  527.         int mid = (lo + hi + 1) / 2;
  528.         if (check(mid))
  529.             lo = mid;
  530.         else
  531.             hi = mid - 1;
  532.     }
  533.     return lo;
  534. }
  535.  
  536.  
  537. // =============================================================================
  538. // 10) MINIMUM LEXICOGRAPHIC ROTATION
  539. // =============================================================================
  540.  
  541. /**
  542.  * Purpose:
  543.  *   Find the starting index of the lexicographically smallest rotation
  544.  *   of a string.
  545.  *
  546.  * Input:
  547.  *   s : the string (non‑empty).
  548.  * Output:
  549.  *   The 0‑based index where the smallest rotation begins.
  550.  * Time Complexity:
  551.  *   O(n log n) (by building the suffix array of s+s).
  552.  * How it works:
  553.  *   Build the string t = s + s. The smallest rotation is the prefix of length n
  554.  *   of the smallest suffix of t that starts at a position < n.
  555.  */
  556. int minRotation(const string& s) {
  557.     int n = (int)s.size();
  558.     string t = s + s;
  559.     vector<int> sa = buildSuffixArray(t);
  560.     for (int pos : sa) {
  561.         if (pos < n) return pos;
  562.     }
  563.     return 0; // never reached
  564. }
  565.  
  566.  
  567. // =============================================================================
  568. // 11) COMPARE TWO SUBSTRINGS IN O(1)
  569. // =============================================================================
  570.  
  571. /**
  572.  * Purpose:
  573.  *   Compare two substrings of the same string (both of equal length)
  574.  *   lexicographically.
  575.  *
  576.  * Input:
  577.  *   s    : the original string
  578.  *   sa   : suffix array of s
  579.  *   rank : rank array (rank[pos] = index in SA)
  580.  *   rmq  : LCPRMQ object built from the LCP array
  581.  *   i, j : starting positions (0‑based)
  582.  *   len  : length of both substrings (i+len <= n, j+len <= n)
  583.  * Output:
  584.  *   -1 if s[i..i+len-1] < s[j..j+len-1]
  585.  *    0 if equal
  586.  *   +1 if greater.
  587.  * Time Complexity:
  588.  *   O(1)
  589.  */
  590. int compareSubstrings(const string& s, const vector<int>& sa,
  591.                       const vector<int>& rank, const LCPRMQ& rmq,
  592.                       int i, int j, int len) {
  593.     int n = (int)s.size();
  594.     if (i == j) return 0;
  595.     int common = lcpBetweenPositions(s, sa, rank, rmq, i, j);
  596.     if (common >= len) return 0;
  597.     return (s[i + common] < s[j + common]) ? -1 : 1;
  598. }
  599.  
  600.  
  601. // =============================================================================
  602. // 12) LONGEST SUBSTRING WITH AT LEAST K OCCURRENCES
  603. // =============================================================================
  604.  
  605. /**
  606.  * Purpose:
  607.  *   Find the length of the longest substring that appears at least k times
  608.  *   in the string (overlapping occurrences are allowed).
  609.  *
  610.  * Input:
  611.  *   s : the string
  612.  *   k : minimum number of occurrences required (k >= 2)
  613.  * Output:
  614.  *   Maximum length of such a substring, or 0 if none.
  615.  * Time Complexity:
  616.  *   O(n log n) for SA+LCP, then O(n) using a sliding window (deque) over
  617.  *   the LCP array.
  618.  * Notes:
  619.  *   The answer is the maximum, over all windows of k-1 consecutive LCP values,
  620.  *   of the minimum LCP in that window.
  621.  */
  622. int longestSubstringWithAtLeastKOccurrences(const string& s, int k) {
  623.     int n = (int)s.size();
  624.     if (k <= 1) return n;
  625.     if (k > n) return 0;
  626.     vector<int> sa = buildSuffixArray(s);
  627.     vector<int> lcp = buildLCP(s, sa);
  628.     int m = (int)lcp.size();
  629.     if (m < k-1) return 0;
  630.  
  631.     deque<int> dq;
  632.     int ans = 0;
  633.     for (int i = 0; i < m; i++) {
  634.         // maintain deque with increasing values of LCP
  635.         while (!dq.empty() && lcp[dq.back()] >= lcp[i]) dq.pop_back();
  636.         dq.push_back(i);
  637.         // remove elements that fall out of the window of size k-1
  638.         if (dq.front() <= i - (k-1)) dq.pop_front();
  639.         // when we have processed at least k-1 elements, the front is the minimum
  640.         if (i >= k-2) {
  641.             ans = max(ans, lcp[dq.front()]);
  642.         }
  643.     }
  644.     return ans;
  645. }
  646.  
  647.  
  648. // =============================================================================
  649. // 13) BUILD BOTH SUFFIX ARRAY AND LCP TOGETHER (convenience)
  650. // =============================================================================
  651.  
  652. /**
  653.  * Purpose:
  654.  *   Builds the suffix array and the LCP array in one call.
  655.  *
  656.  * Input:
  657.  *   s : the string.
  658.  * Output:
  659.  *   A pair {sa, lcp}.
  660.  * Time Complexity:
  661.  *   O(n log n) for SA, O(n) for LCP.
  662.  */
  663. pair<vector<int>, vector<int>> buildSAandLCP(const string& s) {
  664.     vector<int> sa = buildSuffixArray(s);
  665.     vector<int> lcp = buildLCP(s, sa);
  666.     return {sa, lcp};
  667. }
  668.  
  669.  
  670. // =============================================================================
  671. // 14) EXAMPLE USAGE (main)
  672. // =============================================================================
  673.  
  674. int main() {
  675.     ios::sync_with_stdio(false);
  676.     cin.tie(nullptr);
  677.  
  678.     string s = "banana";
  679.     vector<int> sa = buildSuffixArray(s);
  680.     cout << "Suffix Array:\n";
  681.     for (int pos : sa) cout << pos << " ";
  682.     cout << "\n";
  683.  
  684.     vector<int> lcp = buildLCP(s, sa);
  685.     cout << "LCP Array:\n";
  686.     for (int x : lcp) cout << x << " ";
  687.     cout << "\n";
  688.  
  689.     cout << "Distinct substrings: " << countDistinctSubstrings(s) << "\n";
  690.     cout << "Longest repeated: " << longestRepeatedSubstring(s) << "\n";
  691.     cout << "Occurrences of 'ana': " << countOccurrences(s, sa, "ana") << "\n";
  692.     auto occ = findOccurrences(s, sa, "ana");
  693.     cout << "Positions: ";
  694.     for (int p : occ) cout << p << " ";
  695.     cout << "\n";
  696.  
  697.     // LCP between suffixes at positions 1 and 3
  698.     vector<int> rank(s.size());
  699.     for (int i = 0; i < (int)sa.size(); i++) rank[sa[i]] = i;
  700.     LCPRMQ rmq(lcp);
  701.     cout << "LCP(1,3) = " << lcpBetweenPositions(s, sa, rank, rmq, 1, 3) << "\n";
  702.  
  703.     cout << "Minimum rotation of 'banana': " << minRotation(s) << "\n";
  704.  
  705.     string s1 = "abcdef", s2 = "zcdemf";
  706.     cout << "LCS between abcdef and zcdemf: " << longestCommonSubstring(s1, s2) << "\n";
  707.  
  708.     cout << "Longest substring with at least 2 occurrences in 'banana': "
  709.          << longestSubstringWithAtLeastKOccurrences(s, 2) << "\n";
  710.  
  711.     return 0;
  712. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Suffix Array:
5 3 1 0 4 2 
LCP Array:
1 3 0 0 2 
Distinct substrings: 15
Longest repeated: 3
Occurrences of 'ana': 2
Positions: 3 1 
LCP(1,3) = 3
Minimum rotation of 'banana': 5
LCS between abcdef and zcdemf: 3
Longest substring with at least 2 occurrences in 'banana': 3
https://ideone.com/p8uJGI
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

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!