kmpSearch static method

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

Implementation

static int kmpSearch(String text, String pattern) {
  var m = pattern.length;
  var n = text.length;
  if (pattern.isEmpty) {
    return -1;
  }
  // j: the current index of pattern
  var j = 0;
  for (var it = 0; it < n; it++) {
    var i = it;
    while (j > 0 && text[i] != pattern[j]) {
      j = pi(j - 1, pattern = pattern);
    }
    if (text[i] == pattern[j]) {
      j++;
    }
    if (j == m) {
      return i - m + 1;
    }
  }
  return -1;
}