fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. // =======================================================================
  7. // DEFINITIONS (read this first)
  8. // =======================================================================
  9. //
  10. // - Prefix: a substring that starts at index 0.
  11. // - Proper prefix: a prefix that is NOT equal to the whole string.
  12. // - Suffix: a substring that ends at the last index.
  13. // - Border: a string that is both a prefix and a suffix.
  14. //   Example: in "abcab", "ab" is a border.
  15. // - pi[i]: length of the longest proper border of the prefix ending at i.
  16. //   This is the core of KMP.
  17. // - State in KMP: the length of the longest prefix of the pattern that is
  18. //   a suffix of the processed text.
  19. // - Period: a positive integer p such that the string can be formed by
  20. //   repeating its prefix of length p.
  21. // =======================================================================
  22.  
  23. // =======================================================================
  24. // 1) Prefix Function (pi) – the heart of KMP
  25. // =======================================================================
  26.  
  27. // buildPrefixFunction
  28. // --------------------
  29. // What it does:
  30. //   Computes the prefix function (pi array) for a given pattern.
  31. //   pi[i] = length of the longest proper prefix of pattern[0..i]
  32. //   that is also a suffix of pattern[0..i].
  33. //
  34. // Input:
  35. //   pattern: a string (or vector, see generic section).
  36. //
  37. // Output:
  38. //   vector<int> pi, size = pattern.size().
  39. //   pi[0] is always 0.
  40. //
  41. // Time complexity: O(m) where m = pattern.size().
  42. //
  43. // Constraints:
  44. //   pattern must not be empty (returns empty vector if empty).
  45. //
  46. // Notes:
  47. //   You rarely call this directly; it is used internally by all KMP functions.
  48. vector<int> buildPrefixFunction(const string& p) {
  49.     int m = (int)p.size();
  50.     vector<int> pi(m, 0);
  51.     for (int i = 1; i < m; ++i) {
  52.         int j = pi[i - 1];
  53.         while (j > 0 && p[i] != p[j]) j = pi[j - 1];
  54.         if (p[i] == p[j]) ++j;
  55.         pi[i] = j;
  56.     }
  57.     return pi;
  58. }
  59.  
  60. // =======================================================================
  61. // 2) Basic Pattern Search
  62. // =======================================================================
  63.  
  64. // kmpSearch
  65. // ----------
  66. // What it does:
  67. //   Finds all starting positions (0-indexed) where 'pattern' occurs
  68. //   inside 'text'. Overlapping occurrences are both reported.
  69. //
  70. // Input:
  71. //   text: the string to search in.
  72. //   pattern: the string to search for.
  73. //
  74. // Output:
  75. //   vector<int> positions: each position is the start index of an occurrence.
  76. //   If pattern does not occur, the vector is empty.
  77. //
  78. // Time complexity: O(n + m) where n = text.size(), m = pattern.size().
  79. //
  80. // Constraints:
  81. //   pattern must not be empty. If pattern is empty, the behaviour is undefined
  82. //   (we return empty vector).
  83. //
  84. // Notes:
  85. //   This is the standard KMP search. Overlapping is allowed.
  86. vector<int> kmpSearch(const string& text, const string& pattern) {
  87.     vector<int> res;
  88.     int n = (int)text.size(), m = (int)pattern.size();
  89.     if (m == 0) return res;
  90.     vector<int> pi = buildPrefixFunction(pattern);
  91.     int j = 0;
  92.     for (int i = 0; i < n; ++i) {
  93.         while (j > 0 && text[i] != pattern[j]) j = pi[j - 1];
  94.         if (text[i] == pattern[j]) ++j;
  95.         if (j == m) {
  96.             res.push_back(i - m + 1);
  97.             j = pi[j - 1];  // allow overlapping
  98.         }
  99.     }
  100.     return res;
  101. }
  102.  
  103. // =======================================================================
  104. // 3) Counting Occurrences
  105. // =======================================================================
  106.  
  107. // countOverlapping
  108. // -----------------
  109. // What it does:
  110. //   Counts how many times 'pattern' appears in 'text' allowing overlaps.
  111. //
  112. // Input:
  113. //   text, pattern: strings.
  114. //
  115. // Output:
  116. //   int: number of overlapping occurrences.
  117. //
  118. // Time complexity: O(n + m).
  119. //
  120. // Constraints: pattern must not be empty.
  121. //
  122. // Notes: simply returns kmpSearch(text, pattern).size().
  123. int countOverlapping(const string& text, const string& pattern) {
  124.     return (int)kmpSearch(text, pattern).size();
  125. }
  126.  
  127. // countNonOverlapping
  128. // --------------------
  129. // What it does:
  130. //   Counts the maximum number of occurrences of 'pattern' in 'text'
  131. //   such that no two occurrences overlap.
  132. //
  133. // Input:
  134. //   text, pattern: strings.
  135. //
  136. // Output:
  137. //   int: maximum number of non-overlapping occurrences.
  138. //
  139. // Time complexity: O(n + m).
  140. //
  141. // Constraints: pattern must not be empty.
  142. //
  143. // Notes:
  144. //   Uses a greedy approach: take the leftmost occurrence, then the next
  145. //   one that starts after it ends.
  146. int countNonOverlapping(const string& text, const string& pattern) {
  147.     vector<int> pos = kmpSearch(text, pattern);
  148.     if (pos.empty()) return 0;
  149.     int cnt = 1;
  150.     int last = pos[0];
  151.     int m = (int)pattern.size();
  152.     for (int i = 1; i < (int)pos.size(); ++i) {
  153.         if (pos[i] >= last + m) {
  154.             ++cnt;
  155.             last = pos[i];
  156.         }
  157.     }
  158.     return cnt;
  159. }
  160.  
  161. // =======================================================================
  162. // 4) Borders and Periodicity
  163. // =======================================================================
  164.  
  165. // longestBorder
  166. // --------------
  167. // What it does:
  168. //   Returns the length of the longest proper border of the whole pattern.
  169. //   That is pi[m-1].
  170. //
  171. // Input:
  172. //   pattern: string.
  173. //
  174. // Output:
  175. //   int: length of longest border.
  176. //
  177. // Time complexity: O(m) (builds prefix function).
  178. //
  179. // Constraints: pattern not empty.
  180. //
  181. // Notes:
  182. //   If pattern has no border, returns 0.
  183. int longestBorder(const string& pattern) {
  184.     vector<int> pi = buildPrefixFunction(pattern);
  185.     return pi.empty() ? 0 : pi.back();
  186. }
  187.  
  188. // allBorders
  189. // -----------
  190. // What it does:
  191. //   Returns all lengths of borders of the pattern, from longest to shortest.
  192. //
  193. // Input:
  194. //   pattern: string.
  195. //
  196. // Output:
  197. //   vector<int> border lengths, excluding 0.
  198. //
  199. // Time complexity: O(m).
  200. //
  201. // Constraints: pattern not empty.
  202. //
  203. // Notes:
  204. //   Example: pattern = "ababa" → borders: "aba" (3), "a" (1) → returns [3,1].
  205. vector<int> allBorders(const string& pattern) {
  206.     vector<int> pi = buildPrefixFunction(pattern);
  207.     vector<int> borders;
  208.     int len = pi.back();
  209.     while (len > 0) {
  210.         borders.push_back(len);
  211.         len = pi[len - 1];
  212.     }
  213.     return borders;
  214. }
  215.  
  216. // smallestPeriod
  217. // ---------------
  218. // What it does:
  219. //   Finds the smallest period p such that the string consists of repetitions
  220. //   of its prefix of length p.
  221. //
  222. // Input:
  223. //   s: string.
  224. //
  225. // Output:
  226. //   int: the smallest period length. If no period smaller than n, returns n.
  227. //
  228. // Time complexity: O(n).
  229. //
  230. // Constraints: s not empty.
  231. //
  232. // Notes:
  233. //   Example: "ababab" → period = 2.
  234. //   Uses: period = n - pi[n-1]; if n % period == 0, answer is period.
  235. int smallestPeriod(const string& s) {
  236.     int n = (int)s.size();
  237.     vector<int> pi = buildPrefixFunction(s);
  238.     int period = n - pi[n - 1];
  239.     if (n % period == 0) return period;
  240.     return n;
  241. }
  242.  
  243. // isPeriodic
  244. // -----------
  245. // What it does:
  246. //   Checks if the string is made of repetitions of a smaller block.
  247. //
  248. // Input:
  249. //   s: string.
  250. //
  251. // Output:
  252. //   bool: true if s is periodic (period < n), false otherwise.
  253. //
  254. // Time complexity: O(n).
  255. bool isPeriodic(const string& s) {
  256.     return smallestPeriod(s) < (int)s.size();
  257. }
  258.  
  259. // =======================================================================
  260. // 5) KMP Automaton (Deterministic Finite Automaton)
  261. // =======================================================================
  262.  
  263. // buildKMPAutomaton
  264. // ------------------
  265. // What it does:
  266. //   Builds a transition table for the KMP automaton of a fixed pattern.
  267. //   The automaton has states 0..m where m = pattern.size().
  268. //   State 0: no prefix matched. State m: pattern matched completely.
  269. //   For each state and each character, it gives the next state after reading
  270. //   that character.
  271. //
  272. // Input:
  273. //   pattern: a lowercase English string.
  274. //   alphabetSize: number of distinct characters, default 26 (a..z).
  275. //
  276. // Output:
  277. //   vector<vector<int>> automaton of size (m+1) x alphabetSize.
  278. //   automaton[state][c] = next state (0..m).
  279. //
  280. // Time complexity: O(m * alphabetSize).
  281. //
  282. // Constraints:
  283. //   - Works for lowercase English letters only.
  284. //   - If you need another alphabet, change the character mapping inside.
  285. //
  286. // Notes:
  287. //   This automaton is useful for DP problems (e.g., counting strings that
  288. //   avoid a pattern) or for fast repeated searching.
  289. //   The transition from state m (full match) is defined using the fallback
  290. //   of the last character, which is standard for continued matching.
  291. vector<vector<int>> buildKMPAutomaton(const string& pattern, int alphabetSize = 26) {
  292.     int m = (int)pattern.size();
  293.     vector<vector<int>> aut(m + 1, vector<int>(alphabetSize, 0));
  294.     if (m == 0) return aut;  // not meaningful
  295.     vector<int> pi = buildPrefixFunction(pattern);
  296.  
  297.     for (int state = 0; state <= m; ++state) {
  298.         for (int c = 0; c < alphabetSize; ++c) {
  299.             if (state < m && c == pattern[state] - 'a') {
  300.                 aut[state][c] = state + 1;
  301.             } else if (state == 0) {
  302.                 aut[state][c] = 0;
  303.             } else {
  304.                 aut[state][c] = aut[pi[state - 1]][c];
  305.             }
  306.         }
  307.     }
  308.     return aut;
  309. }
  310.  
  311. // =======================================================================
  312. // 6) DP with KMP Automaton
  313. // =======================================================================
  314.  
  315. // countStringsAvoidPattern
  316. // -------------------------
  317. // What it does:
  318. //   Counts the number of strings of a given length over an alphabet of size
  319. //   'alphabetSize' that do NOT contain 'pattern' as a substring.
  320. //
  321. // Input:
  322. //   len: length of the strings to count.
  323. //   pattern: the forbidden pattern (lowercase English).
  324. //   alphabetSize: number of letters (e.g., 2 for binary, 26 for English).
  325. //   MOD: modulo value (use 1e9+7 or similar).
  326. //
  327. // Output:
  328. //   long long: count modulo MOD.
  329. //
  330. // Time complexity: O(len * m * alphabetSize), where m = pattern.size().
  331. //
  332. // Constraints:
  333. //   pattern must not be empty. alphabetSize should be ≤ 26 if using default
  334. //   buildKMPAutomaton. For larger alphabets, adapt the automaton.
  335. //
  336. // Notes:
  337. //   This is a classic DP on KMP automaton. You can also count strings that
  338. //   contain the pattern at least once by subtracting from total.
  339. ll countStringsAvoidPattern(int len, const string& pattern, int alphabetSize, ll MOD) {
  340.     int m = (int)pattern.size();
  341.     if (m == 0) return 0;  // undefined
  342.     vector<vector<int>> aut = buildKMPAutomaton(pattern, alphabetSize);
  343.     vector<vector<ll>> dp(len + 1, vector<ll>(m + 1, 0));
  344.     dp[0][0] = 1;
  345.     for (int i = 0; i < len; ++i) {
  346.         for (int state = 0; state < m; ++state) {  // avoid state m (match)
  347.             if (dp[i][state] == 0) continue;
  348.             for (int c = 0; c < alphabetSize; ++c) {
  349.                 int ns = aut[state][c];
  350.                 if (ns == m) continue;  // would contain pattern, skip
  351.                 dp[i + 1][ns] = (dp[i + 1][ns] + dp[i][state]) % MOD;
  352.             }
  353.         }
  354.     }
  355.     ll ans = 0;
  356.     for (int state = 0; state < m; ++state) {
  357.         ans = (ans + dp[len][state]) % MOD;
  358.     }
  359.     return ans;
  360. }
  361.  
  362. // =======================================================================
  363. // 7) Advanced Tricks (appeared in ECPC / ACPC)
  364. // =======================================================================
  365.  
  366. // prefixOccurrences
  367. // ------------------
  368. // What it does:
  369. //   For each prefix length i (1..m) of the pattern, count how many times
  370. //   that prefix appears as a substring inside the text.
  371. //
  372. // Input:
  373. //   text, pattern: strings.
  374. //
  375. // Output:
  376. //   vector<int> cnt of size m+1, where cnt[i] = number of occurrences of
  377. //   pattern[0..i-1] in text.
  378. //   cnt[0] is meaningless (ignore it).
  379. //
  380. // Time complexity: O(n + m).
  381. //
  382. // Constraints: pattern not empty.
  383. //
  384. // Notes:
  385. //   This uses a well-known trick: during KMP search, increment cnt[state] for
  386. //   each position; then propagate counts through the border links.
  387. //   Example: text = "aaaa", pattern = "aa" → cnt[1]=3, cnt[2]=3? Actually
  388. //   prefix "a" appears 4 times? The function counts substrings of length i,
  389. //   so "a" appears 4 times, "aa" appears 3 times. Let's test.
  390. vector<int> prefixOccurrences(const string& text, const string& pattern) {
  391.     int m = (int)pattern.size();
  392.     vector<int> cnt(m + 1, 0);
  393.     if (m == 0) return cnt;
  394.     vector<int> pi = buildPrefixFunction(pattern);
  395.     int j = 0;
  396.     for (char c : text) {
  397.         while (j > 0 && c != pattern[j]) j = pi[j - 1];
  398.         if (c == pattern[j]) ++j;
  399.         cnt[j]++;           // state j was reached
  400.         if (j == m) {
  401.             j = pi[j - 1];  // fall back for overlapping
  402.         }
  403.     }
  404.     // Propagate counts through the border tree
  405.     for (int i = m; i >= 1; --i) {
  406.         cnt[pi[i - 1]] += cnt[i];
  407.     }
  408.     return cnt;  // cnt[0] is ignored
  409. }
  410.  
  411. // removeOccurrences
  412. // ------------------
  413. // What it does:
  414. //   Removes all occurrences of 'pattern' from 'text'. After a removal,
  415. //   the remaining parts are concatenated, which may form new occurrences.
  416. //   This function repeatedly removes until no occurrence remains.
  417. //
  418. // Input:
  419. //   text: original string.
  420. //   pattern: pattern to remove.
  421. //
  422. // Output:
  423. //   string: the final string after removing all occurrences.
  424. //
  425. // Time complexity: O(n + m) per removal? Actually O(n + m) overall because
  426. //   each character is pushed/popped once using a stack.
  427. //
  428. // Constraints: pattern not empty.
  429. //
  430. // Notes:
  431. //   Uses a stack of characters and the current KMP state. When a match is
  432. //   complete, pop the matched characters from the stack and restore state.
  433. string removeOccurrences(const string& text, const string& pattern) {
  434.     int m = (int)pattern.size();
  435.     if (m == 0) return text;
  436.     vector<int> pi = buildPrefixFunction(pattern);
  437.     string res;
  438.     vector<int> stateStack;   // state after each char in res
  439.     int j = 0;
  440.     for (char c : text) {
  441.         res.push_back(c);
  442.         while (j > 0 && c != pattern[j]) j = pi[j - 1];
  443.         if (c == pattern[j]) ++j;
  444.         stateStack.push_back(j);
  445.         if (j == m) {
  446.             // remove last m chars
  447.             for (int k = 0; k < m; ++k) {
  448.                 res.pop_back();
  449.                 stateStack.pop_back();
  450.             }
  451.             j = stateStack.empty() ? 0 : stateStack.back();
  452.         }
  453.     }
  454.     return res;
  455. }
  456.  
  457. // longestBorderBetween
  458. // ---------------------
  459. // What it does:
  460. //   Given two strings a and b, finds the longest string that is a prefix of a
  461. //   and also a suffix of b.
  462. //
  463. // Input:
  464. //   a, b: strings.
  465. //
  466. // Output:
  467. //   int: length of the longest common prefix/suffix.
  468. //
  469. // Time complexity: O(|a| + |b|).
  470. //
  471. // Constraints: delimiter '#' must not appear in a or b.
  472. //
  473. // Notes:
  474. //   This is useful when you need to concatenate strings and reuse the border.
  475. //   Example: a = "ab", b = "bc" → longest prefix of a that is suffix of b is
  476. //   "b" (length 1).
  477. int longestBorderBetween(const string& a, const string& b) {
  478.     string combined = a + "#" + b;
  479.     vector<int> pi = buildPrefixFunction(combined);
  480.     return pi.back();
  481. }
  482.  
  483. // kmpStateAtEachPosition
  484. // -----------------------
  485. // What it does:
  486. //   For each position i in text, returns the KMP state (length of the longest
  487. //   prefix of pattern that is a suffix of text[0..i]) after processing text[i].
  488. //
  489. // Input:
  490. //   text, pattern: strings.
  491. //
  492. // Output:
  493. //   vector<int> states of size n, where states[i] is the state after reading
  494. //   text[i].
  495. //
  496. // Time complexity: O(n + m).
  497. //
  498. // Constraints: pattern not empty.
  499. //
  500. // Notes:
  501. //   This is useful for DP or when you need the state at every step.
  502. vector<int> kmpStateAtEachPosition(const string& text, const string& pattern) {
  503.     int m = (int)pattern.size();
  504.     vector<int> states;
  505.     if (m == 0) return states;
  506.     vector<int> pi = buildPrefixFunction(pattern);
  507.     int j = 0;
  508.     for (char c : text) {
  509.         while (j > 0 && c != pattern[j]) j = pi[j - 1];
  510.         if (c == pattern[j]) ++j;
  511.         if (j == m) {
  512.             j = pi[j - 1];
  513.         }
  514.         states.push_back(j);
  515.     }
  516.     return states;
  517. }
  518.  
  519. // =======================================================================
  520. // 8) Generic KMP for vectors (e.g., integers)
  521. // =======================================================================
  522.  
  523. // buildPrefixFunction (generic)
  524. // -----------------------------
  525. // Same as string version but works for any vector<T>.
  526. template<typename T>
  527. vector<int> buildPrefixFunction(const vector<T>& p) {
  528.     int m = (int)p.size();
  529.     vector<int> pi(m, 0);
  530.     for (int i = 1; i < m; ++i) {
  531.         int j = pi[i - 1];
  532.         while (j > 0 && p[i] != p[j]) j = pi[j - 1];
  533.         if (p[i] == p[j]) ++j;
  534.         pi[i] = j;
  535.     }
  536.     return pi;
  537. }
  538.  
  539. // kmpSearch (generic)
  540. // -------------------
  541. template<typename T>
  542. vector<int> kmpSearch(const vector<T>& text, const vector<T>& pattern) {
  543.     vector<int> res;
  544.     int n = (int)text.size(), m = (int)pattern.size();
  545.     if (m == 0) return res;
  546.     vector<int> pi = buildPrefixFunction(pattern);
  547.     int j = 0;
  548.     for (int i = 0; i < n; ++i) {
  549.         while (j > 0 && text[i] != pattern[j]) j = pi[j - 1];
  550.         if (text[i] == pattern[j]) ++j;
  551.         if (j == m) {
  552.             res.push_back(i - m + 1);
  553.             j = pi[j - 1];
  554.         }
  555.     }
  556.     return res;
  557. }
  558.  
  559. // countOverlapping (generic)
  560. template<typename T>
  561. int countOverlapping(const vector<T>& text, const vector<T>& pattern) {
  562.     return (int)kmpSearch(text, pattern).size();
  563. }
  564.  
  565. // countNonOverlapping (generic)
  566. template<typename T>
  567. int countNonOverlapping(const vector<T>& text, const vector<T>& pattern) {
  568.     vector<int> pos = kmpSearch(text, pattern);
  569.     if (pos.empty()) return 0;
  570.     int cnt = 1;
  571.     int last = pos[0];
  572.     int m = (int)pattern.size();
  573.     for (int i = 1; i < (int)pos.size(); ++i) {
  574.         if (pos[i] >= last + m) {
  575.             ++cnt;
  576.             last = pos[i];
  577.         }
  578.     }
  579.     return cnt;
  580. }
  581.  
  582. // =======================================================================
  583. // 9) Example usage (optional)
  584. // =======================================================================
  585.  
  586. int main() {
  587.     ios::sync_with_stdio(false);
  588.     cin.tie(nullptr);
  589.  
  590.     // Example 1: search
  591.     string text = "ababcababcabc", pat = "abc";
  592.     vector<int> pos = kmpSearch(text, pat);
  593.     cout << "Occurrences at: ";
  594.     for (int p : pos) cout << p << " ";
  595.     cout << "\n";  // 2, 7, 10
  596.  
  597.     // Example 2: count overlapping
  598.     cout << "Overlapping count: " << countOverlapping("aaaa", "aa") << "\n";  // 3
  599.  
  600.     // Example 3: non-overlapping
  601.     cout << "Non-overlapping count: " << countNonOverlapping("aaaa", "aa") << "\n";  // 2
  602.  
  603.     // Example 4: period
  604.     cout << "Smallest period of 'ababab': " << smallestPeriod("ababab") << "\n";  // 2
  605.  
  606.     // Example 5: automaton DP
  607.     ll mod = 1000000007LL;
  608.     cout << "Binary strings of length 3 avoiding '11': "
  609.          << countStringsAvoidPattern(3, "11", 2, mod) << "\n";  // 5 (000,001,010,100,101)
  610.  
  611.     // Example 6: prefix occurrences
  612.     vector<int> occ = prefixOccurrences("aaaa", "aa");
  613.     cout << "Prefix 'a' occurs " << occ[1] << " times, prefix 'aa' occurs " << occ[2] << " times\n";
  614.  
  615.     // Example 7: remove occurrences
  616.     cout << "Remove 'ab' from 'aabab': " << removeOccurrences("aabab", "ab") << "\n";  // "a"
  617.  
  618.     return 0;
  619. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Occurrences at: 2 7 10 
Overlapping count: 3
Non-overlapping count: 2
Smallest period of 'ababab': 2
Binary strings of length 3 avoiding '11': 8
Prefix 'a' occurs 4 times, prefix 'aa' occurs 3 times
Remove 'ab' from 'aabab': a
https://ideone.com/G83upy
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!