알고리즘 문제 풀이 간 사용한 kmp알고리즘에 대하여 정리를 해보려고 한다.

개요

kmp 알고리즘은 문자열 매칭 알고리즘 중 하나로, 문자열 내에서 특정 패턴을 찾는 알고리즘이다.
긴 문자열에서 특정 패턴을 찾을 때 유용한데 시간 복잡도는 O(n + m)이다.

알고리즘 동작 방식은 다음과 같다.
문자열과 패턴 문자열을 비교하면서 일치하지 않는 부분을 찾아내고 이때, 일치하지 않는 부분만큼 패턴 문자열을 이동시켜 다시 비교하는 것을 반복한다.

주요 개념

• 검색 과정에서 얻는 정보를 버리지 않고 다음 시작 위치를 찾는데 활용
• 접두사도 되고 접미사도 되는 문자열의 최대 길이를 부분 일치 테이블로 만들어서 이를 활용

다음 시작 위치 찾기

불일치가 일어났을 때 지금까지 일치한 글자의 수를 이용해서 다음 시도해야 할 시작위치를 찾아낼 수 있다. 이때 부분 일치 테이블이란 것을 활용하여 다음 시작위치를 찾아낼 수 있는데 부분일치테이블에 대해서 알아보기 전에 먼저 어떻게 다음 위치를 찾아내는지 부터 생각을 해본다면
먼저, 어떤 긴 문자열에서 특정 패턴을 찾는데 현재 i번째에서부터 i + j번째까지 일치하고 i + j + 1번째에서 불일치가 일어났다고 가정을 한다면 완전 탐색으로 접근을 한다면 단순히 i + 1부터 특정 패턴의 처음과 다시 비교해서 일치하는지 확인할 수 있다.

그런데 그렇게 하지 않더라도 다음 시작 위치를 찾을 수 있다는 것이 key point인데 이때, N의 각 접두사에 대해서 접두사도 되고 접미사도 되는 문자열의 최대 길이를 계산하면 다음 시작 위치를 알 수 있다.

문자열 H(검색 대상 문자열) 중 일부분과 N(특정 패턴)의 일부분이 matched만큼 일치한다면 N[:matched]와 H[i: i + matched]는 일치하게 된다.
이때, i + k위치가 시작위치가 되기 위해서는 N[k:matched] == N[:k]를 만족하는 k가 다음 시작위치가 될 수 있는데 이 중 가장 큰 문자열의 길이만큼 건너뛰어서 확인이 가능하다. 해당 조건을 만족하는 것을 미리 만들어 놓는데 이것이 바로 부분 일치 테이블이다.(partial table, pi)

동작 방식

1. 시작 위치에서 0에서부터 시작해서 일치하는지 여부를 확인한다.
2. 만약 일치하지 않는다면
   a. 하나도 일치하지 않는다면 다음 위치를 탐색 한다.
   b. 그렇지 않다면 다음으로 시작해야 할 위치로 건너뛴다. 이때 다음으로 시작해야 할 위치와의 차이는 pi[일치한 수]이다.
   matched - pi[일치한 수]만큼 건너 뛰는데 matched는 항상 pi[matched]보다 크다.
3. 만약 일치한다면
   a. matched를 증가시킨다.
   b. matched 수가 문자열의 길이라면 전체를 찾은 것이므로 다음 시작 칸으로 이동한다.

구현

function kmp(a,b) {
	let n = a.length, m = b.length;
    const pi = getPartial(b);
    const ret = [];
    
    let begin = 0,matched = 0;
    while(begin + matched < n) {
    	if(matched < m && a[begin + matched] === b[matched]) {
        	matched+=1;
            if(matched === n) {
            	ret.push(begin);
            }
        } else {
        	if(matched === 0) {
            	begin += 1;
            } else {
            	begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
}
function getPartial(a) {
	const n = a.length;
    let begin = 1, matched = 0;
    const ret = Array.from({length:n},() => 0);
    
    while(begin + matched < n) {
    	if(a[begin + matched] === a[matched]) {
        matched++;
        ret[begin + matched - 1] = matched;
        } else {
        	if(matched===0) {
	            begin += 1;
            } else {
            	begin += matched - ret[matched - 1];
                matched = ret[matched - 1];
            }
        }
    }
    return ret;    
}