fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ===================================================================
  5. // This file provides two Aho‑Corasick implementations:
  6. //   1) SimpleAhoCorasick  – memory‑efficient, only total match counts
  7. //   2) AdvancedAhoCorasick – full per‑pattern counts, distinct patterns,
  8. //      longest pattern, replacement, and DP helpers.
  9. //
  10. // Read the comments above each struct and its methods to understand:
  11. //   - What it solves
  12. //   - Input / output
  13. //   - Time complexity
  14. //   - Preconditions
  15. // ===================================================================
  16.  
  17. const int ALPHABET = 26;  // only lowercase 'a'..'z' is supported
  18.  
  19. // ===================================================================
  20. // 1) SIMPLE AHO‑CORASICK (total matches only)
  21. // ===================================================================
  22. // Purpose:
  23. //   Build a trie from patterns and compute failure links.
  24. //   Provides fast scanning to count total occurrences of *any* pattern.
  25. // Memory:
  26. //   O(total_length_of_patterns) nodes.
  27. // Each node stores:
  28. //   - next[ALPHABET] : transitions (pre‑computed after build)
  29. //   - fail           : failure link
  30. //   - out            : number of patterns ending exactly at this node
  31. //   - output_link    : nearest node in the fail‑chain that has out>0
  32. //   - depth          : depth in the trie (used for longest match)
  33. // ===================================================================
  34.  
  35. struct SimpleAhoCorasick {
  36.     vector<array<int, ALPHABET>> next;
  37.     vector<int> fail, out, output_link, depth;
  38.  
  39.     SimpleAhoCorasick() {
  40.         // root = state 0
  41.         next.push_back({});
  42.         fail.push_back(0);
  43.         out.push_back(0);
  44.         output_link.push_back(0);
  45.         depth.push_back(0);
  46.     }
  47.  
  48.     // Add one pattern (multiple identical patterns are allowed – out counts them).
  49.     void addPattern(const string &s) {
  50.         int node = 0;
  51.         for (char c : s) {
  52.             int idx = c - 'a';
  53.             if (!next[node][idx]) {
  54.                 next[node][idx] = next.size();
  55.                 next.push_back({});
  56.                 fail.push_back(0);
  57.                 out.push_back(0);
  58.                 output_link.push_back(0);
  59.                 depth.push_back(depth[node] + 1);
  60.             }
  61.             node = next[node][idx];
  62.         }
  63.         out[node]++;
  64.     }
  65.  
  66.     // Build failure links and pre‑compute transitions.
  67.     // Must be called after all patterns are added and before any search.
  68.     void build() {
  69.         queue<int> q;
  70.         // depth 1 nodes: failure goes to root
  71.         for (int c = 0; c < ALPHABET; ++c) {
  72.             int child = next[0][c];
  73.             if (child) {
  74.                 fail[child] = 0;
  75.                 q.push(child);
  76.             }
  77.         }
  78.  
  79.         while (!q.empty()) {
  80.             int v = q.front();
  81.             q.pop();
  82.  
  83.             // Set output_link for v: if out[v]>0 then v itself, else follow fail's output_link.
  84.             if (out[v]) output_link[v] = v;
  85.             else output_link[v] = output_link[fail[v]];
  86.  
  87.             for (int c = 0; c < ALPHABET; ++c) {
  88.                 int u = next[v][c];
  89.                 if (u) {
  90.                     fail[u] = next[fail[v]][c];
  91.                     q.push(u);
  92.                 } else {
  93.                     // Pre‑compute missing transitions for speed.
  94.                     next[v][c] = next[fail[v]][c];
  95.                 }
  96.             }
  97.         }
  98.     }
  99.  
  100.     // 1.1) Total number of occurrences of any pattern in the text.
  101.     //      Overlapping matches are counted separately.
  102.     //      Complexity: O(|text| + total_matches) in worst case.
  103.     long long countTotalMatches(const string &text) const {
  104.         long long ans = 0;
  105.         int state = 0;
  106.         for (char c : text) {
  107.             state = next[state][c - 'a'];
  108.             // Traverse the output‑link chain to add all patterns ending here.
  109.             for (int v = output_link[state]; v != 0; v = output_link[fail[v]]) {
  110.                 ans += out[v];
  111.             }
  112.         }
  113.         return ans;
  114.     }
  115.  
  116.     // 1.2) Find the earliest ending index (0‑based) where any pattern appears.
  117.     //      Returns -1 if none.
  118.     //      Complexity: O(|text|).
  119.     int firstMatchEnd(const string &text) const {
  120.         int state = 0;
  121.         for (int i = 0; i < (int)text.size(); ++i) {
  122.             state = next[state][text[i] - 'a'];
  123.             if (output_link[state] != 0) return i;  // at least one pattern ends at i
  124.         }
  125.         return -1;
  126.     }
  127.  
  128.     // 1.3) Check whether any pattern appears in the text.
  129.     //      Complexity: O(|text|) with early exit.
  130.     bool containsAny(const string &text) const {
  131.         int state = 0;
  132.         for (char c : text) {
  133.             state = next[state][c - 'a'];
  134.             if (output_link[state] != 0) return true;
  135.         }
  136.         return false;
  137.     }
  138.  
  139.     // 1.4) For each position i, get the length of the longest pattern that ends at i.
  140.     //      Returns a vector of length |text|, where 0 means no pattern ends there.
  141.     //      Complexity: O(|text|).
  142.     vector<int> longestPatternLengthAtEachPos(const string &text) const {
  143.         vector<int> res(text.size(), 0);
  144.         int state = 0;
  145.         for (int i = 0; i < (int)text.size(); ++i) {
  146.             state = next[state][text[i] - 'a'];
  147.             int v = output_link[state];
  148.             if (v) res[i] = depth[v];   // deepest output node = longest pattern
  149.         }
  150.         return res;
  151.     }
  152. };
  153.  
  154. // ===================================================================
  155. // 2) ADVANCED AHO‑CORASICK (full per‑pattern support)
  156. // ===================================================================
  157. // Purpose:
  158. //   Same as simple, but stores the ID(s) of patterns ending at each node.
  159. //   Enables per‑pattern counts, distinct patterns, replacement,
  160. //   DP for counting strings without patterns, etc.
  161. // Memory:
  162. //   O(total_length_of_patterns + total_number_of_patterns).
  163. // ===================================================================
  164.  
  165. struct AdvancedAhoCorasick {
  166.     vector<array<int, ALPHABET>> next;
  167.     vector<int> fail, depth, output_link;
  168.     vector<vector<int>> pattern_ids;   // list of pattern indices that end at this node
  169.  
  170.     AdvancedAhoCorasick() {
  171.         next.push_back({});
  172.         fail.push_back(0);
  173.         depth.push_back(0);
  174.         output_link.push_back(0);
  175.         pattern_ids.push_back({});
  176.     }
  177.  
  178.     // Add a pattern with a given ID (usually its index in the input list).
  179.     void addPattern(const string &s, int id) {
  180.         int node = 0;
  181.         for (char c : s) {
  182.             int idx = c - 'a';
  183.             if (!next[node][idx]) {
  184.                 next[node][idx] = next.size();
  185.                 next.push_back({});
  186.                 fail.push_back(0);
  187.                 depth.push_back(depth[node] + 1);
  188.                 output_link.push_back(0);
  189.                 pattern_ids.push_back({});
  190.             }
  191.             node = next[node][idx];
  192.         }
  193.         pattern_ids[node].push_back(id);
  194.     }
  195.  
  196.     // Build failure links and pre‑compute transitions.
  197.     void build() {
  198.         queue<int> q;
  199.         for (int c = 0; c < ALPHABET; ++c) {
  200.             int child = next[0][c];
  201.             if (child) {
  202.                 fail[child] = 0;
  203.                 q.push(child);
  204.             }
  205.         }
  206.  
  207.         while (!q.empty()) {
  208.             int v = q.front();
  209.             q.pop();
  210.  
  211.             if (!pattern_ids[v].empty()) output_link[v] = v;
  212.             else output_link[v] = output_link[fail[v]];
  213.  
  214.             for (int c = 0; c < ALPHABET; ++c) {
  215.                 int u = next[v][c];
  216.                 if (u) {
  217.                     fail[u] = next[fail[v]][c];
  218.                     q.push(u);
  219.                 } else {
  220.                     next[v][c] = next[fail[v]][c];
  221.                 }
  222.             }
  223.         }
  224.     }
  225.  
  226.     // 2.1) Count occurrences of each pattern in the text.
  227.     //      Returns a vector of length total_patterns.
  228.     //      Complexity: O(|text| + total_matches).
  229.     vector<int> countOccurrences(const string &text, int total_patterns) const {
  230.         vector<int> ans(total_patterns, 0);
  231.         int state = 0;
  232.         for (char c : text) {
  233.             state = next[state][c - 'a'];
  234.             for (int v = output_link[state]; v != 0; v = output_link[fail[v]]) {
  235.                 for (int id : pattern_ids[v]) {
  236.                     ans[id]++;
  237.                 }
  238.             }
  239.         }
  240.         return ans;
  241.     }
  242.  
  243.     // 2.2) Count how many distinct patterns appear at least once.
  244.     //      Complexity: O(|text| + total_matches).
  245.     int countDistinctPatterns(const string &text, int total_patterns) const {
  246.         vector<char> seen(total_patterns, 0);
  247.         int distinct = 0;
  248.         int state = 0;
  249.         for (char c : text) {
  250.             state = next[state][c - 'a'];
  251.             for (int v = output_link[state]; v != 0; v = output_link[fail[v]]) {
  252.                 for (int id : pattern_ids[v]) {
  253.                     if (!seen[id]) {
  254.                         seen[id] = 1;
  255.                         distinct++;
  256.                     }
  257.                 }
  258.             }
  259.         }
  260.         return distinct;
  261.     }
  262.  
  263.     // 2.3) For each position i, get the length and ID of the longest pattern ending at i.
  264.     //      Returns two vectors: lengths and IDs (‑1 if none).
  265.     //      Complexity: O(|text|).
  266.     pair<vector<int>, vector<int>> longestPatternAtEachPos(const string &text) const {
  267.         int n = text.size();
  268.         vector<int> len(n, 0), id(n, -1);
  269.         int state = 0;
  270.         for (int i = 0; i < n; ++i) {
  271.             state = next[state][text[i] - 'a'];
  272.             int v = output_link[state];
  273.             if (v) {
  274.                 len[i] = depth[v];
  275.                 id[i] = pattern_ids[v][0];   // all patterns at this node have same length
  276.             }
  277.         }
  278.         return {len, id};
  279.     }
  280.  
  281.     // 2.4) Replace all occurrences of any pattern with a replacement string.
  282.     //      Longest match is chosen when overlaps occur.
  283.     //      Complexity: O(|text| + total_replacement_length).
  284.     string replaceOccurrences(const string &text, const string &replacement) const {
  285.         auto [len_arr, id_arr] = longestPatternAtEachPos(text);
  286.         string res;
  287.         int i = 0;
  288.         while (i < (int)text.size()) {
  289.             if (len_arr[i] > 0) {
  290.                 res += replacement;
  291.                 i += len_arr[i];
  292.             } else {
  293.                 res += text[i];
  294.                 i++;
  295.             }
  296.         }
  297.         return res;
  298.     }
  299.  
  300.     // 2.5) Find all starting positions of occurrences of a specific pattern (by ID).
  301.     //      Returns a vector of start indices (0‑based).
  302.     //      Complexity: O(|text| + occurrences_of_target).
  303.     vector<int> findOccurrencesOfPattern(const string &text, int target_id) const {
  304.         vector<int> positions;
  305.         int state = 0;
  306.         for (int i = 0; i < (int)text.size(); ++i) {
  307.             state = next[state][text[i] - 'a'];
  308.             for (int v = output_link[state]; v != 0; v = output_link[fail[v]]) {
  309.                 for (int id : pattern_ids[v]) {
  310.                     if (id == target_id) {
  311.                         positions.push_back(i - depth[v] + 1);
  312.                     }
  313.                 }
  314.             }
  315.         }
  316.         return positions;
  317.     }
  318. };
  319.  
  320. // ===================================================================
  321. // 3) COMMON CONTEST TRICKS (ECPC / ACPC style)
  322. // ===================================================================
  323.  
  324. // 3.1) Count substrings that contain NO pattern (all substrings are "good").
  325. //      For each right endpoint R, find the leftmost L such that [L..R] contains no pattern.
  326. //      Complexity: O(|text| + total_matches) (if using output‑link chain).
  327. long long countGoodSubstrings(const string &text, const AdvancedAhoCorasick &ac) {
  328.     int n = text.size();
  329.     long long ans = 0;
  330.     int state = 0;
  331.     int last_bad = -1;   // rightmost ending position of a pattern seen so far
  332.  
  333.     for (int i = 0; i < n; ++i) {
  334.         state = ac.next[state][text[i] - 'a'];
  335.         // If any pattern ends at i, update last_bad.
  336.         if (ac.output_link[state] != 0) {
  337.             last_bad = i;
  338.         }
  339.         // All substrings ending at i with start > last_bad are good.
  340.         ans += (i - last_bad);
  341.     }
  342.     return ans;
  343. }
  344.  
  345. // 3.2) Count strings of length N over the alphabet that contain NO pattern.
  346. //      Uses DP on the automaton.
  347. //      Complexity: O(N * states * ALPHABET).
  348. long long countStringsWithoutPatterns(int N, const AdvancedAhoCorasick &ac, long long MOD = 1e9+7) {
  349.     int S = ac.next.size();
  350.     vector<char> bad(S, 0);
  351.     // Mark a state as bad if any pattern ends at it or along its fail‑chain.
  352.     for (int v = 0; v < S; ++v) {
  353.         int u = v;
  354.         while (u) {
  355.             if (!ac.pattern_ids[u].empty()) {
  356.                 bad[v] = 1;
  357.                 break;
  358.             }
  359.             u = ac.fail[u];
  360.         }
  361.     }
  362.  
  363.     vector<vector<long long>> dp(N+1, vector<long long>(S, 0));
  364.     dp[0][0] = 1;   // empty string at root
  365.     for (int len = 0; len < N; ++len) {
  366.         for (int state = 0; state < S; ++state) {
  367.             if (bad[state] || dp[len][state] == 0) continue;
  368.             for (int c = 0; c < ALPHABET; ++c) {
  369.                 int nxt = ac.next[state][c];
  370.                 if (!bad[nxt]) {
  371.                     dp[len+1][nxt] = (dp[len+1][nxt] + dp[len][state]) % MOD;
  372.                 }
  373.             }
  374.         }
  375.     }
  376.  
  377.     long long ans = 0;
  378.     for (int state = 0; state < S; ++state) {
  379.         if (!bad[state]) ans = (ans + dp[N][state]) % MOD;
  380.     }
  381.     return ans;
  382. }
  383.  
  384. // 3.3) Count strings of length N that contain AT LEAST ONE pattern.
  385. //      (Total strings - those with no pattern)
  386. long long countStringsWithAtLeastOnePattern(int N, const AdvancedAhoCorasick &ac, long long MOD = 1e9+7) {
  387.     long long total = 1;
  388.     for (int i = 0; i < N; ++i) total = (total * ALPHABET) % MOD;
  389.     long long no = countStringsWithoutPatterns(N, ac, MOD);
  390.     return (total - no + MOD) % MOD;
  391. }
  392.  
  393. // 3.4) Find the length of the longest pattern that appears in the text.
  394. //      Returns {length, pattern_id} (‑1 if none).
  395. pair<int,int> longestPatternInText(const string &text, const AdvancedAhoCorasick &ac) {
  396.     int state = 0;
  397.     int best_len = 0, best_id = -1;
  398.     for (char c : text) {
  399.         state = ac.next[state][c - 'a'];
  400.         for (int v = ac.output_link[state]; v != 0; v = ac.output_link[ac.fail[v]]) {
  401.             if (!ac.pattern_ids[v].empty()) {
  402.                 int len = ac.depth[v];
  403.                 if (len > best_len) {
  404.                     best_len = len;
  405.                     best_id = ac.pattern_ids[v][0];
  406.                 }
  407.             }
  408.         }
  409.     }
  410.     return {best_len, best_id};
  411. }
  412.  
  413. // ===================================================================
  414. // 4) HELPER: build an AdvancedAhoCorasick from a vector of patterns
  415. // ===================================================================
  416.  
  417. AdvancedAhoCorasick buildAC(const vector<string>& patterns) {
  418.     AdvancedAhoCorasick ac;
  419.     for (int i = 0; i < (int)patterns.size(); ++i) {
  420.         ac.addPattern(patterns[i], i);
  421.     }
  422.     ac.build();
  423.     return ac;
  424. }
  425.  
  426. // ===================================================================
  427. // EXAMPLE USAGE (can be removed)
  428. // ===================================================================
  429.  
  430. int main() {
  431.     ios::sync_with_stdio(false);
  432.     cin.tie(nullptr);
  433.  
  434.     vector<string> patterns = {"he", "she", "his", "hers"};
  435.     AdvancedAhoCorasick ac = buildAC(patterns);
  436.  
  437.     string text = "ushers";
  438.     auto counts = ac.countOccurrences(text, patterns.size());
  439.     cout << "Occurrences:\n";
  440.     for (int i = 0; i < (int)patterns.size(); ++i) {
  441.         cout << patterns[i] << ": " << counts[i] << "\n";
  442.     }
  443.  
  444.     cout << "Distinct patterns: " << ac.countDistinctPatterns(text, patterns.size()) << "\n";
  445.  
  446.     auto [len_arr, id_arr] = ac.longestPatternAtEachPos(text);
  447.     cout << "Longest pattern ending at each position:\n";
  448.     for (int i = 0; i < (int)text.size(); ++i) {
  449.         cout << i << ": len=" << len_arr[i] << ", id=" << id_arr[i] << "\n";
  450.     }
  451.  
  452.     string replaced = ac.replaceOccurrences(text, "[MASK]");
  453.     cout << "Replaced text: " << replaced << "\n";
  454.  
  455.     long long good = countGoodSubstrings(text, ac);
  456.     cout << "Number of substrings with no pattern: " << good << "\n";
  457.  
  458.     return 0;
  459. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Occurrences:
he: 1
she: 1
his: 0
hers: 1
Distinct patterns: 3
Longest pattern ending at each position:
0: len=0, id=-1
1: len=0, id=-1
2: len=0, id=-1
3: len=3, id=1
4: len=0, id=-1
5: len=4, id=3
Replaced text: ush[MASK]
Number of substrings with no pattern: 7
https://ideone.com/fNzv6Q
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!