computePi static method

List<int> computePi(
  1. String pattern
)

Implementation

static List<int> computePi(String pattern) {
  int m = pattern.length;
  List<int> pi = List.filled(m, 0);
  int k = 0;

  for (int j = 1; j < m; j++) {
    while (k > 0 && pattern[j] != pattern[k]) {
      // If mismatch occurs, fall back in the pi table
      k = pi[k - 1];
    }
    if (pattern[j] == pattern[k]) {
      // If characters match, increment the length of the prefix
      k++;
    }
    pi[j] = k; // pi[j] is now complete
  }

  return pi;
}