We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Functional Structures
  4. Substring Searching
  5. Discussions

Substring Searching

  • __alexey__
     + 0 comments

    Scala solution works with prefix function as ArrayBuffer.

    Description of pseudocode for the table-building algorithm in the Wikipedia link is not correct.

    Correct algorithm can be found here https://cp-algorithms.com/string/prefix-function.html#implementation

    vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}