KMP 알고리즘 : 문자열 검색

문자열을 검색하는 KMP 알고리즘은 Failure Function 에 대한 이해가 필수다.

Failure Function

 

들어가기 전에, Failure Function 을 포함하여 이 글은 1-based index 를 기반으로 한다.

즉 모든 문자열은 배열의 1번 인덱스부터 담겨 있다고 가정한다.

 

문제 상황은 다음과 같다.

문자열 Str 에서 문자열 Want 가 나타나는 위치를 모두 파악할 수 있을까?

 

Str 의 길이를 S, Want 의 길이를 W이라고 한다면,

제일 단순한 풀이는 Str 의 모든 S 개의 칸에서 출발하여 연속한 W 개의 칸을 Want 와 비교하는 것이다.

이렇게 하면 O(SW) 의 시간이 걸려 비효율적이다.

 

Failure Function만 제대로 이해하고 있다면, 무려 O(S+W) 의 시간복잡도로 해결할 수 있다.

우리는 Want 의 Failure Function 만 구하면 된다. 즉, 찾고 싶은 문자열의 Failure Function 만 구한다.

Str[i] 에서 불일치가 최초로 발생했고, m 개의 문자는 일치한 상황

위 그림을 보자.

순조롭게 일치하다가, i 번째 문자에서 불일치가 발생했고, 그때까지 일치한 문자는 m 개로 하자.

여기서 주의할 점은, m 은 인덱스가 아니라, 그저 여태까지 일치한 문자들의 개수다.

또한 i는, Want 에서의 인덱스가 아닌, Str 에서의 인덱스를 의미한다.

 

불일치가 발생했다고 해서 Want 를 한 칸 오른쪽으로 밀어 다시 검사해야할까? 아니다.

Want 에서 F[m] 을 구해놨기 때문에 이를 이용하자. 그림에서 알 수 있듯 F[m] 은 파란 사각형의 길이다.

m - F[m] 칸 오른쪽으로 Want 를 밀어주자.

파란색 사각형은 서로 일치하기 때문에, 그 일치하는 부분부터 탐색을 이어가면 된다.

이렇게 하면 비효율적인 탐색 없이 효율적인 이동만을 하게 된다.

그럼 Want 를 몇 칸 오른쪽으로 밀면 될까? 그림에서 알 수 있듯이 m - F[m] 칸 밀면 될 것이다!

그리고 Failure Function 의 정의에 의해 우리는 이미 F[m] 개의 문자가 일치한다는 사실을 알고 출발할 수 있다.

 

그러면, 아래의 코드가 쉽게 나온다.

void KMP(){
    int start = 1, m = 0, i;
    while(start + W - 1 <= S){
        for(;m < W;m++){
            if(Str[start + m] != Want[m+1]) break;
        }
        if(m == W) ans.push_back(start);
        start += m - f[m];
        if(m) m = f[m];
    }
}

이제 이 코드를 분석해보자.

 

int start = 1, m = 0, i;

start 는, Str 배열의 몇 번째 원소부터 비교할건지에 대한 변수다.

당연히 1번째 원소부터 비교할 것이기 때문에 start = 1을 넣고 시작하자.

또한 아직 탐색을 시작도 안 한 상태이므로 일치한 문자도 0개다. 따라서 m = 0 으로 초기화 해주자.

 

while(start + W - 1 <= S){

start 부터 비교하면 우리는 start ~ start + W - 1 까지 비교한다. 끝점인 start + W - 1 은 Str 길이를 넘을 수 없다.

 

for(;m < W;m++){
    if(Str[start + m] != Want[m+1]) break;
}
if(m == W) ans.push_back(start);

현재 우리가 확보한 일치 문자는 총 m 개다. 따라서 우리는 m+1번째 문자부터, 일치하는지 확인해야 한다.

예를 들어 for 문이 실행되기 전 m = 3 이었다면, 3개의 문자가 일치한 상태에서 시작하는 것이다.

따라서 우리는 Str[start + 3] 과 Want[4] 를 비교함으로써, 4번째 문자도 일치하는지 확인한다.

 

for문이 끝났는데 m == W 라는 것은 일치한 문자 개수가 Want 의 길이와 같다는 뜻이다.

즉 Want 를 완전히 찾은 상태이므로 ans 에 시작 인덱스인 start 를 넣어준다.

 

start += m - f[m];
if(m) m = f[m];

위에서 기술한 대로, 우리는 start 를 m - f[m] 칸 밀어주면 된다.

또한, 그렇게 민다면 우리는 f[m] 개의 일치문자를 확보한 상태이므로 m = f[m] 으로 만들어준다.

 

나는 f[0] = -1 으로 하는 방식이라 m 이 0 이 아닐때만 m = f[m] 으로 해주었다.

f[0] = -1 로 해주면 m == 0 일때에도 start 가 자동으로 1 늘어나기 때문에 편리하다.

---

또 다른 KMP 구현은 아래와 같은 방식이다.

 

BOJ 10747 Censoring 을 풀다가 떠오른 방법인데, start 를 변화시키지 않고 하는 것이다.

위 방법처럼 KMP 를 구현하면 BOJ 10747 문제를 풀기가 조금 까다로웠다. (나의 기준)

위 그림을 다시 보자. 우리는 원래 위 그림을 Want 를 m - F[m] 칸 오른쪽으로 민다고 해석했다.

하지만, 이 그림을 Want[m+1] != Str[i] 였으니, 이번에는 Want[F[m]+1] 과 Str[i] 를 비교해본다고 생각할 수 있다.

만약 이번에도 Want[F[m]+1] != Str[i] 가 되면, 이제는 Want[F[F[m]]+1] 과 Str[i] 를 비교하는 방식이다.

같은 과정이지만 다른 해석인 셈이다.

 

코드는 아래와 같다.

void KMP(){
    int i = 1, m = 0;
    while(i <= S){
        for(;i <= S; i++, m++){
            if(m == W || Str[i] != Want[m+1]) break;
        }
        if(m == W) ans.push_back(i - W);

        if(!m) i++;
        else m = f[m];
    }
}

 

코드를 분석해보자.

 

int i = 1, m = 0;

i 는 위에서 언급한대로 "불일치가 발생하는 Str 의 인덱스" 이다. 1번 인덱스부터 출발하니 시작은 1이다.

m 은 항상 그랬듯 "현재까지 일치한 문자의 개수"이다. 당연히 아직은 일치한 것이 없으므로 시작은 0이다.

 

 while(i <= S){

i 는 S의 불일치 발생 인덱스다. 비교 시작 인덱스가 아니므로, i 는 S 이하면 다 된다.

 

for(;i <= S; i++, m++){
    if(m == W || Str[i] != Want[m+1]) break;
}
if(m == W) ans.push_back(i - W);

현재 m 개는 일치한 상황이므로 다음 문자인 Want[m+1] 부터 비교한다.

만약 W 개가 일치하거나, Str[i] 와 지금 보고 있는 Want[m+1] 이 다르다면 바로 break 한다.

 

for 문이 끝난 후 m == W 라면 답을 찾았으므로, 비교시작 인덱스인 i - m 을 답에 추가한다.

( i 는 불일치 인덱스이므로 시작 인덱스 + W 로 되어있을 것 )

 

if(!m) i++;
else m = f[m];

m == 0 이 된 것은 Str[i] 는 가만히 있고 m -> F[m] -> F[F[m]] ->... 로 갔는데도 일치하지 않아 결국 0이 됐다는 뜻이다.

즉 더 이상 Str[i] 를 일치시킬 수 없기 때문에 i++ 시키고 m은 그대로 0 으로 남게 한다. (일치한 것이 없으므로)

 

만약 m 이 0 이 아니라는 것은 불일치된 Str[i] 에 도전할 수 있는 F[m] 이 남아 있다는 것이다.

따라서 m = F[m] 으로 만들어주고 다시 for 문으로 보내 Str[i] 와 일치하는지 확인한다.