buildLPS function

List<int> buildLPS(String pattern)

Builds the Longest Prefix Suffix (LPS) array used in KMP algorithm.

For each position, LPS indicates the length of the longest proper prefix which is also a suffix for the substring ending at that position.

Time complexity: O(m), where m is length of the pattern.

Implementation

List<int> buildLPS(String pattern) {
  int length = 0; // length of the previous longest prefix suffix
  int i = 1;
  List<int> lps = List.filled(pattern.length, 0);

  while (i < pattern.length) {
    if (pattern[i] == pattern[length]) {
      length++;
      lps[i] = length;
      i++;
    } else {
      if (length != 0) {
        length = lps[length - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }

  return lps;
}