길이가 M
인 문자열 내에 길이가 N
인 단어가 있는지 확인하는 알고리즘
단어 내에 동일한 패턴의 문자가 반복될 경우, 이미 확인이 끝난 패턴의 재확인을 피하기 위해 패턴 테이블을 만든다.
패턴 테이블
abcaby
a !== b
이므로 0a !== c
이므로 0a === a
이므로 1b === b
이므로 2c !== y
이므로 0[0, 0, 0, 1, 2, 0]
const createPatternTable = (pattern) => {
const patternLength = pattern.length;
const patternTable = Array(patternLength).fill(0);
for (let i = 1; i < patternLength; i++) {
if (patternTable[i - 1] === 0) {
if (pattern[0] === pattern[i]) {
patternTable[i] = 1;
}
} else {
if (pattern[patternTable[i - 1]] === pattern[i]) {
patternTable[i] = patternTable[i - 1] + 1;
} else {
if (pattern[0] === pattern[i]) {
patternTable[i] = 1;
}
}
}
}
return patternTable;
};
완성된 패턴 테이블을 활용하여 문자열에서 단어를 검색한다.
const KMPAlgorithm = (text, pattern) => {
const length = text.length;
const patternLength = pattern.length;
const table = createPatternTable(pattern);
let textIndex = 0;
let tableIndex = 0;
let counter = 0;
let answer = -1;
while (length + tableIndex - textIndex >= patternLength && answer === -1) {
if (text[textIndex + counter] === pattern[tableIndex + counter]) {
counter += 1;
if (tableIndex + counter === patternLength) {
answer = textIndex - tableIndex;
}
} else {
textIndex = counter > 0 ? textIndex + counter : textIndex + 1;
tableIndex =
tableIndex + counter - 1 >= 0 ? table[tableIndex + counter - 1] : 0;
counter = 0;
}
}
return answer;
};