kmp-substring.js

function kmpSearch(str, pattern) {
  var arr = calculatePrefixTable(pattern);
  var j = 0;
  var i = 0;
  var index = -1;
  var len = pattern.length;
  var strLength = str.length;
  while(i < strLength) {
    if(str.charAt(i) === pattern.charAt(j)) {
      i++;
      j++;
    } else {
      if(j !== 0) {
        j = arr[j - 1];
      } else {
        i++;
      }
    }
    if(j === len) {
      index = i - j;
      break;
    }
  }

  return index;
}

function calculatePrefixTable(pattern) {
  var result = [];
  var j = 0;
  var i = j + 1;
  var len = pattern.length;
  result.length = len;
  result.fill(0);
  while(i < len) {
    if(pattern.charAt(i) === pattern.charAt(j)) {
      result[i] = j + 1;
      i++;
      j++;
    } else {
      if(j !== 0) {
        j = result[j - 1];
      } else {
        i++;
      }
    }
  }
  return result;
}


kmpSearch('ABABDABACDABABCABAB', 'ABABCABAB')