fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ===================================================================
  5. // This file contains a collection of Z-Algorithm and related string 
  6. // matching algorithms. Each function is ready to be used as a "black box".
  7. // Read the comments above each one to understand:
  8. //   - What it solves
  9. //   - What input it expects
  10. //   - What it returns
  11. //   - Time complexity
  12. //   - Important constraints / assumptions
  13. // ===================================================================
  14.  
  15.  
  16. // ===================================================================
  17. // 1) Z-Algorithm (Core)
  18. //    The Z-array (or Z-function) of a string s is an array z where
  19. //    z[i] = the length of the longest substring starting at i that 
  20. //    matches the prefix of s.
  21. // 
  22. //    Example: s = "aaaaa"
  23. //      z[1] = 4 (s[0..3] == s[1..4])
  24. //      z[2] = 3 (s[0..2] == s[2..4])
  25. //      z[3] = 2
  26. //      z[4] = 1
  27. //
  28. //    Example: s = "abcab"
  29. //      z[3] = 2 (s[0..1] == s[3..4] = "ab")
  30. // ===================================================================
  31.  
  32. // 1.1) Compute the Z-array for a given string.
  33. //      Parameters:
  34. //        - s: the input string.
  35. //      Returns:
  36. //        - a vector<int> where z[i] is the Z-value at index i.
  37. //          By definition, z[0] is usually set to 0 (or n, both are common;
  38. //          here we set it to 0).
  39. //      Time complexity: O(n) where n = s.length().
  40. //      Constraint: none.
  41. //      Note: This is the core function. All other functions in this file
  42. //            build on top of it.
  43. vector<int> zAlgorithm(const string& s) {
  44.     int n = s.size();
  45.     vector<int> z(n, 0);
  46.     int l = 0, r = 0; // [l, r] is the current Z-box (the rightmost segment that matches the prefix)
  47.     for (int i = 1; i < n; i++) {
  48.         if (i <= r) {
  49.             z[i] = min(r - i + 1, z[i - l]);
  50.         }
  51.         while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
  52.             z[i]++;
  53.         }
  54.         if (i + z[i] - 1 > r) {
  55.             l = i;
  56.             r = i + z[i] - 1;
  57.         }
  58.     }
  59.     return z;
  60. }
  61.  
  62. // ===================================================================
  63. // 2) Pattern Matching using Z-Algorithm
  64. //    The most common use of Z is to find all occurrences of a pattern
  65. //    inside a text in O(n + m) time.
  66. // ===================================================================
  67.  
  68. // 2.1) Find all starting positions where pattern 'pat' occurs in 'text'.
  69. //      Parameters:
  70. //        - text: the string to search in.
  71. //        - pat: the pattern string to look for.
  72. //      Returns:
  73. //        - vector<int> containing all indices (0-based) in 'text' 
  74. //          where 'pat' starts.
  75. //      Time complexity: O(|text| + |pat|).
  76. //      Constraint: none.
  77. //      Note: This function uses the trick: concatenate pat + '#' + text,
  78. //            where '#' is a character that does not appear in either.
  79. //            Then z[i] == |pat| means that pat appears at position (i - |pat| - 1) in text.
  80. vector<int> findPatternOccurrences(const string& text, const string& pat) {
  81.     string combined = pat + "#" + text;
  82.     vector<int> z = zAlgorithm(combined);
  83.     int m = pat.size();
  84.     vector<int> occurrences;
  85.     for (int i = m + 1; i < (int)z.size(); i++) {
  86.         if (z[i] == m) {
  87.             // The pattern starts at this position in 'text'
  88.             occurrences.push_back(i - m - 1);
  89.         }
  90.     }
  91.     return occurrences;
  92. }
  93.  
  94. // 2.2) Count how many times 'pat' appears in 'text' (non-overlapping occurrences).
  95. //      Parameters:
  96. //        - text: the string to search in.
  97. //        - pat: the pattern string.
  98. //      Returns:
  99. //        - the number of times 'pat' appears as a substring (non-overlapping).
  100. //      Time complexity: O(|text| + |pat|).
  101. //      Constraint: none.
  102. //      Note: This is different from just counting all occurrences because
  103. //            it skips overlapping ones. For example, in "aaaa", pattern "aa"
  104. //            appears 3 times overlapping, but non-overlapping only 2 times.
  105. int countNonOverlappingOccurrences(const string& text, const string& pat) {
  106.     vector<int> occ = findPatternOccurrences(text, pat);
  107.     if (occ.empty()) return 0;
  108.     int cnt = 0;
  109.     int lastEnd = -1;
  110.     for (int pos : occ) {
  111.         if (pos >= lastEnd) {
  112.             cnt++;
  113.             lastEnd = pos + pat.size();
  114.         }
  115.     }
  116.     return cnt;
  117. }
  118.  
  119. // ===================================================================
  120. // 3) Advanced Z-Algorithm Applications
  121. //    These are common problems that can be solved with Z.
  122. // ===================================================================
  123.  
  124. // 3.1) Find the longest substring that appears at least twice in a string.
  125. //      Parameters:
  126. //        - s: the input string.
  127. //      Returns:
  128. //        - the length of the longest substring that appears in at least two
  129. //          different positions (overlapping allowed).
  130. //      Time complexity: O(n).
  131. //      Constraint: none.
  132. //      Note: The answer is simply the maximum value in the Z-array (except z[0]).
  133. int longestSubstringAppearingTwice(const string& s) {
  134.     vector<int> z = zAlgorithm(s);
  135.     int ans = 0;
  136.     for (int i = 1; i < (int)z.size(); i++) {
  137.         ans = max(ans, z[i]);
  138.     }
  139.     return ans;
  140. }
  141.  
  142. // 3.2) Find the lexicographically smallest rotation of a string.
  143. //      Parameters:
  144. //        - s: the input string.
  145. //      Returns:
  146. //        - the lexicographically smallest rotation of s.
  147. //      Time complexity: O(n) using Booth's algorithm.
  148. //      Constraint: none.
  149. //      Note: The previous Z-only implementation was incorrect for some cases.
  150. //            This version is correct and still runs in O(n).
  151. string lexicographicallySmallestRotation(const string& s) {
  152.     // Booth's algorithm for minimal string rotation
  153.     string doubled = s + s;
  154.     int n = s.size();
  155.     int i = 0, j = 1, k = 0;
  156.     while (i < n && j < n && k < n) {
  157.         char a = doubled[i + k];
  158.         char b = doubled[j + k];
  159.         if (a == b) {
  160.             k++;
  161.         } else if (a < b) {
  162.             j += k + 1;
  163.             if (j <= i) j = i + 1;
  164.             k = 0;
  165.         } else {
  166.             i += k + 1;
  167.             if (i <= j) i = j + 1;
  168.             k = 0;
  169.         }
  170.     }
  171.     int start = min(i, j);
  172.     return s.substr(start) + s.substr(0, start);
  173. }
  174.  
  175. // 3.3) Count the number of distinct substrings of a string.
  176. //      Parameters:
  177. //        - s: the input string.
  178. //      Returns:
  179. //        - the total number of distinct non-empty substrings of s.
  180. //      Time complexity: O(n) with suffix automaton or O(n log n) with suffix array.
  181. //      This placeholder returns 0. For large n, use suffix array + LCP (provided below).
  182. //      An O(n^2) Z-based method exists but is too slow for n > 5000.
  183. long long countDistinctSubstringsZ(const string& s) {
  184.     // Not implemented – use the suffix array + LCP functions instead.
  185.     return 0;
  186. }
  187.  
  188. // ===================================================================
  189. // 4) Z-Algorithm for Arrays (Generalization)
  190. //    The Z-algorithm works on any sequence of comparable elements,
  191. //    not just characters. Below is a generic version that works on vectors.
  192. // ===================================================================
  193.  
  194. // 4.1) Compute Z-array for a vector of integers (or any comparable type).
  195. //      Parameters:
  196. //        - vec: a vector of elements (must support the == operator).
  197. //      Returns:
  198. //        - vector<int> z where z[i] is the Z-value for the vector.
  199. //      Time complexity: O(n).
  200. //      Constraint: The elements must be comparable with '=='.
  201. //      Note: This is useful for pattern matching on arrays, e.g., finding
  202. //            a subarray pattern inside an array.
  203. template<typename T>
  204. vector<int> zAlgorithmArray(const vector<T>& vec) {
  205.     int n = vec.size();
  206.     vector<int> z(n, 0);
  207.     int l = 0, r = 0;
  208.     for (int i = 1; i < n; i++) {
  209.         if (i <= r) {
  210.             z[i] = min(r - i + 1, z[i - l]);
  211.         }
  212.         while (i + z[i] < n && vec[z[i]] == vec[i + z[i]]) {
  213.             z[i]++;
  214.         }
  215.         if (i + z[i] - 1 > r) {
  216.             l = i;
  217.             r = i + z[i] - 1;
  218.         }
  219.     }
  220.     return z;
  221. }
  222.  
  223. // 4.2) Find all occurrences of a pattern array inside a text array.
  224. //      Parameters:
  225. //        - text: the vector to search in.
  226. //        - pat: the pattern vector.
  227. //      Returns:
  228. //        - vector<int> of starting indices where 'pat' occurs in 'text'.
  229. //      Time complexity: O(|text| + |pat|).
  230. //      Constraint: The element types must be comparable with '=='.
  231. //      Note: Uses a sentinel that must not appear in the data. Here we use -1,
  232. //            change it if your arrays can contain -1.
  233. vector<int> findPatternOccurrencesArray(const vector<int>& text, const vector<int>& pat) {
  234.     vector<int> combined;
  235.     combined.reserve(pat.size() + 1 + text.size());
  236.     for (int x : pat) combined.push_back(x);
  237.     combined.push_back(-1); // sentinel (must not appear in text or pat)
  238.     for (int x : text) combined.push_back(x);
  239.     vector<int> z = zAlgorithmArray(combined);
  240.     int m = pat.size();
  241.     vector<int> occ;
  242.     for (int i = m + 1; i < (int)z.size(); i++) {
  243.         if (z[i] == m) {
  244.             occ.push_back(i - m - 1);
  245.         }
  246.     }
  247.     return occ;
  248. }
  249.  
  250. // ===================================================================
  251. // 5) KMP (Knuth-Morris-Pratt) Algorithm
  252. //    KMP is another linear-time string matching algorithm, similar to Z.
  253. //    It uses a prefix function (pi) instead of Z.
  254. //    I include it here because it is often used together with Z.
  255. // ===================================================================
  256.  
  257. // 5.1) Compute the prefix function (pi) for a string.
  258. //      Parameters:
  259. //        - s: the input string.
  260. //      Returns:
  261. //        - vector<int> pi where pi[i] = the length of the longest proper
  262. //          prefix of s[0..i] that is also a suffix of s[0..i].
  263. //      Time complexity: O(n).
  264. //      Constraint: none.
  265. //      Note: pi[0] is always 0.
  266. vector<int> computePrefixFunction(const string& s) {
  267.     int n = s.size();
  268.     vector<int> pi(n, 0);
  269.     for (int i = 1; i < n; i++) {
  270.         int j = pi[i - 1];
  271.         while (j > 0 && s[i] != s[j]) {
  272.             j = pi[j - 1];
  273.         }
  274.         if (s[i] == s[j]) j++;
  275.         pi[i] = j;
  276.     }
  277.     return pi;
  278. }
  279.  
  280. // 5.2) Find all occurrences of a pattern in a text using KMP.
  281. //      Parameters:
  282. //        - text: the string to search in.
  283. //        - pat: the pattern string.
  284. //      Returns:
  285. //        - vector<int> of starting indices.
  286. //      Time complexity: O(|text| + |pat|).
  287. //      Constraint: none.
  288. //      Note: This is an alternative to Z-based matching. KMP can be more
  289. //            memory-efficient because it does not need to store the full Z-array.
  290. vector<int> kmpPatternOccurrences(const string& text, const string& pat) {
  291.     if (pat.empty()) return {};
  292.     string combined = pat + "#" + text;
  293.     vector<int> pi = computePrefixFunction(combined);
  294.     int m = pat.size();
  295.     vector<int> occ;
  296.     for (int i = m + 1; i < (int)pi.size(); i++) {
  297.         if (pi[i] == m) {
  298.             occ.push_back(i - 2 * m);
  299.         }
  300.     }
  301.     return occ;
  302. }
  303.  
  304. // 5.3) Find the period of a string (the smallest period).
  305. //      Parameters:
  306. //        - s: the input string.
  307. //      Returns:
  308. //        - the length of the smallest period.
  309. //        - The period p means s[i] = s[i + p] for all i < n - p.
  310. //      Time complexity: O(n).
  311. //      Constraint: none.
  312. //      Note: If the string has no period, the answer is n.
  313. //            For example, "abcabc" has period 3.
  314. //            "aaaa" has period 1.
  315. int smallestPeriodKMP(const string& s) {
  316.     int n = s.size();
  317.     vector<int> pi = computePrefixFunction(s);
  318.     int p = n - pi[n - 1];
  319.     if (n % p == 0) return p;
  320.     return n;
  321. }
  322.  
  323. // ===================================================================
  324. // 6) Manacher's Algorithm (Palindromic Substrings)
  325. //    While not Z, Manacher is another linear-time string algorithm that
  326. //    is often needed in the same problems. I include it here for completeness.
  327. // ===================================================================
  328.  
  329. // 6.1) Manacher's algorithm to find the longest palindromic substring.
  330. //      Parameters:
  331. //        - s: the input string.
  332. //      Returns:
  333. //        - the longest palindromic substring.
  334. //      Time complexity: O(n).
  335. //      Constraint: none.
  336. //      Note: This algorithm also gives the radius of all palindromes.
  337. string longestPalindromeManacher(const string& s) {
  338.     // Transform s: insert '#' between characters and at ends.
  339.     // e.g., "abc" -> "#a#b#c#"
  340.     string t = "#";
  341.     for (char c : s) {
  342.         t += c;
  343.         t += '#';
  344.     }
  345.     int n = t.size();
  346.     vector<int> p(n, 0); // p[i] = radius of the palindrome centered at i
  347.     int center = 0, right = 0;
  348.     for (int i = 0; i < n; i++) {
  349.         int mirror = 2 * center - i;
  350.         if (i < right) {
  351.             p[i] = min(right - i, p[mirror]);
  352.         }
  353.         // Expand
  354.         while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i - p[i] - 1] == t[i + p[i] + 1]) {
  355.             p[i]++;
  356.         }
  357.         // Update center and right
  358.         if (i + p[i] > right) {
  359.             center = i;
  360.             right = i + p[i];
  361.         }
  362.     }
  363.     // Find the maximum radius
  364.     int maxLen = 0;
  365.     int bestCenter = 0;
  366.     for (int i = 0; i < n; i++) {
  367.         if (p[i] > maxLen) {
  368.             maxLen = p[i];
  369.             bestCenter = i;
  370.         }
  371.     }
  372.     // Recover the original string
  373.     int start = (bestCenter - maxLen) / 2;
  374.     return s.substr(start, maxLen);
  375. }
  376.  
  377. // ===================================================================
  378. // 7) Rolling Hash (Rabin-Karp)
  379. //    Not strictly Z, but it is a very common technique for string matching
  380. //    and is often used in ECPC/ACPC problems.
  381. // ===================================================================
  382.  
  383. // 7.1) Compute the hash of a string using a rolling hash technique.
  384. //      Parameters:
  385. //        - s: the input string.
  386. //      Returns:
  387. //        - a vector of long long hashes (prefix hashes).
  388. //      Time complexity: O(n).
  389. //      Constraint: Uses two moduli to reduce collisions. Assumes lowercase letters.
  390. //      Note: This is a double-hash implementation. Change the base or moduli if needed.
  391. struct RollingHash {
  392.     static const long long BASE = 31;
  393.     static const long long MOD1 = 1000000007;
  394.     static const long long MOD2 = 1000000009;
  395.     vector<long long> pow1, pow2, hash1, hash2;
  396.  
  397.     RollingHash(const string& s) {
  398.         int n = s.size();
  399.         pow1.resize(n + 1);
  400.         pow2.resize(n + 1);
  401.         hash1.resize(n + 1);
  402.         hash2.resize(n + 1);
  403.         pow1[0] = pow2[0] = 1;
  404.         for (int i = 0; i < n; i++) {
  405.             pow1[i + 1] = (pow1[i] * BASE) % MOD1;
  406.             pow2[i + 1] = (pow2[i] * BASE) % MOD2;
  407.             hash1[i + 1] = (hash1[i] * BASE + (s[i] - 'a' + 1)) % MOD1;
  408.             hash2[i + 1] = (hash2[i] * BASE + (s[i] - 'a' + 1)) % MOD2;
  409.         }
  410.     }
  411.  
  412.     // Returns the pair of hashes for substring s[l..r] (0-based, inclusive).
  413.     pair<long long, long long> getHash(int l, int r) {
  414.         long long h1 = (hash1[r + 1] - (hash1[l] * pow1[r - l + 1]) % MOD1 + MOD1) % MOD1;
  415.         long long h2 = (hash2[r + 1] - (hash2[l] * pow2[r - l + 1]) % MOD2 + MOD2) % MOD2;
  416.         return {h1, h2};
  417.     }
  418. };
  419.  
  420. // ===================================================================
  421. // 8) Suffix Array (with LCP)
  422. //    This is a more advanced data structure, but it is very powerful.
  423. //    I include the basics here for reference.
  424. // ===================================================================
  425.  
  426. // 8.1) Build a suffix array for a string.
  427. //      Parameters:
  428. //        - s: the input string.
  429. //      Returns:
  430. //        - vector<int> sa where sa[i] is the starting index of the i-th suffix
  431. //          in lexicographic order.
  432. //      Time complexity: O(n log n) using the doubling algorithm.
  433. //      Constraint: none.
  434. //      Note: This is a simplified version using sorting with pairs.
  435. //            For ECPC/ACPC, O(n log^2 n) might be acceptable for n up to 1e5.
  436. vector<int> buildSuffixArray(const string& s) {
  437.     int n = s.size();
  438.     vector<int> sa(n), rank(n), tmp(n);
  439.     for (int i = 0; i < n; i++) {
  440.         sa[i] = i;
  441.         rank[i] = s[i];
  442.     }
  443.     for (int k = 1; k < n; k <<= 1) {
  444.         auto cmp = [&](int i, int j) {
  445.             if (rank[i] != rank[j]) return rank[i] < rank[j];
  446.             int ri = (i + k < n) ? rank[i + k] : -1;
  447.             int rj = (j + k < n) ? rank[j + k] : -1;
  448.             return ri < rj;
  449.         };
  450.         sort(sa.begin(), sa.end(), cmp);
  451.         tmp[sa[0]] = 0;
  452.         for (int i = 1; i < n; i++) {
  453.             tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
  454.         }
  455.         rank = tmp;
  456.         if (rank[sa[n - 1]] == n - 1) break;
  457.     }
  458.     return sa;
  459. }
  460.  
  461. // 8.2) Build the LCP (Longest Common Prefix) array for a suffix array.
  462. //      Parameters:
  463. //        - s: the original string.
  464. //        - sa: the suffix array.
  465. //      Returns:
  466. //        - vector<int> lcp where lcp[i] = LCP of sa[i] and sa[i+1].
  467. //      Time complexity: O(n).
  468. //      Constraint: The suffix array must be valid.
  469. vector<int> buildLCPArray(const string& s, const vector<int>& sa) {
  470.     int n = s.size();
  471.     vector<int> rank(n);
  472.     for (int i = 0; i < n; i++) {
  473.         rank[sa[i]] = i;
  474.     }
  475.     vector<int> lcp(n - 1);
  476.     int h = 0;
  477.     for (int i = 0; i < n; i++) {
  478.         if (rank[i] == 0) continue;
  479.         int j = sa[rank[i] - 1];
  480.         while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
  481.         lcp[rank[i] - 1] = h;
  482.         if (h > 0) h--;
  483.     }
  484.     return lcp;
  485. }
  486.  
  487. // ===================================================================
  488. // 9) Tricks & Patterns that appeared in ECPC/ACPC
  489. //    These are common ideas that use Z or related algorithms.
  490. // ===================================================================
  491.  
  492. // 9.1) Check if a string is a concatenation of multiple copies of a pattern.
  493. //      Parameters:
  494. //        - s: the input string.
  495. //      Returns:
  496. //        - true if s can be written as p + p + ... + p for some pattern p.
  497. //      Time complexity: O(n).
  498. //      Constraint: none.
  499. //      Note: This uses the prefix function to find the period.
  500. bool isPowerOfString(const string& s) {
  501.     int n = s.size();
  502.     vector<int> pi = computePrefixFunction(s);
  503.     int p = n - pi[n - 1];
  504.     return (n % p == 0);
  505. }
  506.  
  507. // 9.2) Find the number of times a string is repeated in a pattern.
  508. //      Parameters:
  509. //        - s: the input string.
  510. //      Returns:
  511. //        - the maximum k such that s is a repetition of some string p, k times.
  512. //      Time complexity: O(n).
  513. //      Constraint: none.
  514. //      Note: For "abcabcabc", answer is 3 (p = "abc").
  515. int maxRepetitions(const string& s) {
  516.     int n = s.size();
  517.     vector<int> pi = computePrefixFunction(s);
  518.     int p = n - pi[n - 1];
  519.     if (n % p == 0) return n / p;
  520.     return 1;
  521. }
  522.  
  523. // 9.3) Z-algorithm on prefix sums? Not exactly, but sometimes we use Z on
  524. //      transformed arrays. For example, comparing differences between elements.
  525. //      Problem: Find the longest subarray that is a "mountain" or matches a pattern.
  526. //      We can use Z on an array of differences (s[i+1] - s[i]) to find
  527. //      matching patterns.
  528. //
  529. //      Example: Given an array, find the longest subarray that is a repeating
  530. //               pattern of "up, down, up, down...".
  531. //      We can encode the array as a string of '+' and '-' signs and use Z.
  532. //      But that is problem-specific.
  533. //      I will not implement it generically, but mention it.
  534.  
  535. // ===================================================================
  536. // 10) Advanced: Counting substrings where no character appears more than
  537. //     k times (using two pointers + hash) – not Z, but common in ECPC.
  538. //     I include it because it is a common trick.
  539. // ===================================================================
  540.  
  541. // 10.1) Count substrings with at most K distinct characters.
  542. //       This is already covered in the Two Pointers template, but I include
  543. //       it here for reference.
  544. long long countSubstringsAtMostKDistinct(const string& s, int k) {
  545.     int n = s.size();
  546.     unordered_map<char, int> freq;
  547.     int l = 0;
  548.     long long ans = 0;
  549.     for (int r = 0; r < n; r++) {
  550.         freq[s[r]]++;
  551.         while ((int)freq.size() > k) {
  552.             freq[s[l]]--;
  553.             if (freq[s[l]] == 0) freq.erase(s[l]);
  554.             l++;
  555.         }
  556.         ans += (r - l + 1);
  557.     }
  558.     return ans;
  559. }
  560.  
  561. // ===================================================================
  562. // 11) Helper: Z-array for string with wildcard matching? (Advanced)
  563. //     Sometimes problems ask to match patterns with '?' wildcard.
  564. //     We can use Z with a custom comparator that treats '?' as matching any char.
  565. //     This is not implemented here because it requires a modified Z algorithm.
  566. // ===================================================================
  567.  
  568. // ===================================================================
  569. // 12) "MUBIS" – This term is not standard. Perhaps it refers to "Multiplicative"?
  570. //     Or it could be an acronym from a specific contest.
  571. //     I will assume you meant "Multiplicative" or "Minimum Unique Prefix"?
  572. //     If it's an ECPC-specific term, please clarify. I will add a placeholder.
  573. // ===================================================================
  574.  
  575. // 12.1) Placeholder for MUBIS-related function.
  576. //       If you provide more details, I can implement it.
  577. int mubisFunction(const string& s) {
  578.     // TODO: Implement MUBIS if you provide more details.
  579.     return 0;
  580. }
  581.  
  582. // ===================================================================
  583. // main() with example usage (you can ignore this part)
  584. // ===================================================================
  585.  
  586. int main() {
  587.     ios::sync_with_stdio(false);
  588.     cin.tie(nullptr);
  589.  
  590.     // Example 1: Z-algorithm
  591.     string s = "ababab";
  592.     vector<int> z = zAlgorithm(s);
  593.     cout << "Z-array for " << s << ": ";
  594.     for (int x : z) cout << x << " ";
  595.     cout << "\n";
  596.  
  597.     // Example 2: Pattern matching
  598.     string text = "abababab";
  599.     string pat = "aba";
  600.     vector<int> occ = findPatternOccurrences(text, pat);
  601.     cout << "Occurrences of '" << pat << "' in '" << text << "': ";
  602.     for (int pos : occ) cout << pos << " ";
  603.     cout << "\n";
  604.  
  605.     // Example 3: Longest palindrome
  606.     string pal = "babad";
  607.     cout << "Longest palindrome in " << pal << ": " << longestPalindromeManacher(pal) << "\n";
  608.  
  609.     // Example 4: Lexicographically smallest rotation
  610.     string rot = "bca";
  611.     cout << "Smallest rotation of " << rot << ": " << lexicographicallySmallestRotation(rot) << "\n";
  612.  
  613.     // Example 5: KMP period
  614.     string period = "abcabcabc";
  615.     cout << "Smallest period of " << period << ": " << smallestPeriodKMP(period) << "\n";
  616.  
  617.     return 0;
  618. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Z-array for ababab: 0 0 4 0 2 0 
Occurrences of 'aba' in 'abababab': 0 2 4 
Longest palindrome in babad: bab
Smallest rotation of bca: abc
Smallest period of abcabcabc: 3
https://ideone.com/JVJwcl
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!