kmpSearch function

int kmpSearch(String text, String pattern)

Performs KMP search of pattern within text.

Returns the starting index of the first occurrence of pattern in text. Returns -1 if the pattern is not found.

Time complexity: O(n), where n is length of text.

Example:

int index = kmpSearch("abxabcabcaby", "abcaby");
print(index); // 6

Implementation

int kmpSearch(String text, String pattern) {
  int n = text.length;
  int m = pattern.length;

  if (m == 0) return 0; // empty pattern matches at index 0

  List<int> lps = buildLPS(pattern);

  int i = 0; // index for text
  int j = 0; // index for pattern

  while (i < n) {
    if (text[i] == pattern[j]) {
      i++;
      j++;
    }

    if (j == m) {
      return i - j; // pattern found at index (i - j)
    } else if (i < n && text[i] != pattern[j]) {
      if (j != 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }

  return -1; // pattern not found
}