Prefix function, Knuth-Morris-Pratt algorithm

Prefix function definition

 

$$ \pi[i] = \max_{k=0 ... i} k: s[0 ... k - 1] = s[i - (k - 1) ... i) \text{ for string }s$$

 

 

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;
}

 

 

Application 

 

1. Search for a substring in a string, the Knuth-Morris-Pratt algorithm

 

If we want to find a string s in a string t,

make a new string 's + padding (filled with characters, not in s and t) + t',

and get the prefix function of the new string. 

 

Then, we just find the prefix function value which equals the length of the string s for ith.

 

int count_s_in_t(string s, string t) {
  vector<int> prefix_function_values = prefix_function(s + "$$$$" + t);
  int s_length = s.length();
  int ret = 0;
  for (auto value: prefix_function_values) {
    ret += (value == s_length);
  }
  return ret;
}

 

 

2. Counting the number of occurrences of each prefix

vector<int> get_occurrence (string s) {
  vector<int> pi = prefix_function(s);
  
  int n = s.length();
  vector<int> ans(n + 1);
  for (int i = 0; i < n; i++) {
    ans[pi[i]]++;
  }
  for (int i = n - 1; i > 0; i--) {
    ans[pi[i - 1]] += ans[i];
  }
  for (int i = 1; i <= n; i++) {
    ans[i]++;
  }
  return ans;
}