kmpSearch static method

int kmpSearch(
  1. String text,
  2. String pattern
)

Implementation

static int kmpSearch(String text, String pattern) {
  if (pattern.isEmpty) {
    return 0; // If pattern is empty, return 0 as it matches at the start
  }

  int m = pattern.length;
  int n = text.length;
  List<int> piTable = computePi(pattern); // Precompute the pi table
  int j = 0; // j is the index in pattern

  for (int i = 0; i < n; i++) {
    while (j > 0 && text[i] != pattern[j]) {
      // If mismatch occurs, use the pi table to skip characters
      j = piTable[j - 1];
    }
    if (text[i] == pattern[j]) {
      // If characters match, move to the next character in pattern
      j++;
    }
    if (j == m) {
      // If we have matched the whole pattern
      return i - m + 1; // Return the start index of the match
    }
  }

  return -1; // No match found
}