«Строка KMP» относится к алгоритму Кнута-Морриса-Пратта, который представляет собой эффективный алгоритм сопоставления с образцом, используемый для поиска вхождений строки шаблона в большую текстовую строку. В JavaScript существует несколько способов реализации алгоритма KMP. Вот пример реализации:

Метод 1: реализация алгоритма KMP

function buildPatternTable(pattern) {
  const table = [0];
  let prefixIndex = 0;
  let suffixIndex = 1;
  while (suffixIndex < pattern.length) {
    if (pattern[prefixIndex] === pattern[suffixIndex]) {
      table[suffixIndex] = prefixIndex + 1;
      suffixIndex++;
      prefixIndex++;
    } else if (prefixIndex === 0) {
      table[suffixIndex] = 0;
      suffixIndex++;
    } else {
      prefixIndex = table[prefixIndex - 1];
    }
  }
  return table;
}
function kmpSearch(text, pattern) {
  const patternTable = buildPatternTable(pattern);
  let textIndex = 0;
  let patternIndex = 0;
  while (textIndex < text.length) {
    if (pattern[patternIndex] === text[textIndex]) {
      if (patternIndex === pattern.length - 1) {
        return textIndex - pattern.length + 1; // Match found
      }
      patternIndex++;
      textIndex++;
    } else if (patternIndex > 0) {
      patternIndex = patternTable[patternIndex - 1];
    } else {
      textIndex++;
    }
  }
  return -1; // No match found
}
// Example usage:
const text = "ABABDABACDABABCABAB";
const pattern = "ABABCABAB";
const matchIndex = kmpSearch(text, pattern);
console.log("Match found at index:", matchIndex);

Метод 2: использование метода indexOf

function kmpSearch(text, pattern) {
  const matchIndex = text.indexOf(pattern);
  return matchIndex;
}
// Example usage:
const text = "ABABDABACDABABCABAB";
const pattern = "ABABCABAB";
const matchIndex = kmpSearch(text, pattern);
console.log("Match found at index:", matchIndex);