알고리즘 : 스트링 탐색 #2 (KMP 알고리즘)

지난 시간에는 한 글자씩 대조하여 스트링을 탐색하는 직선적 알고리즘을 알아보았습니다.

이번에 소개할 KMP 알고리즘은 이와 달리 패턴에서 얻은 어떠한 정보를 바탕으로 텍스트를 껑충껑충 넘어가며 패턴과 비교를 진행하는데, 어떻게 진행되는 지 알아보도록 하겠습니다.

---

위의 그림과 같이 "ABCDABCDABEF" 에서 "ABCDABE" 를 찾으려 합니다.

지난 시간에 알아본 직선적 알고리즘으로 탐색하다 보면 마지막 C, E에서 불일치가 일어나죠.

그렇다면 아래와 같이 딱 한 칸만 이동하여 또 비교를 진행합니다.

이렇게 진행하면 시간낭비가 된다는 걸 그냥 봐도 알 수 있습니다.

이런 시간낭비를 개발자 형님들은 그냥 두고 볼 수가 없었죠. 결국 더 간결하고 시간이 훨씬 적게 드는 탐색 알고리즘을 발견했으며, 발견자인 Knuth, Morris, Pratt의 이름을 따 KMP 알고리즘이라고 부릅니다.

그렇다면 KMP 알고리즘을 적용했을 땐 어떻게 됐을까요?

놀랍게도 한번에 ABCD를 뛰어넘어 버립니다. KMP 알고리즘은 이렇게 패턴과 겹치는 부분이 있다면 뛰어넘을 수 있죠.

텍스트를 뛰어넘을 수 있는 정보는 패턴에서 어떠한 배열을 구하면 되는데, 

KMP 알고리즘은 패턴에서 정보를 얻는 InitNext, 이를 바탕으로 비교를 진행하는 KMP로 크게 두 파트로 나뉩니다.

---

Next 배열 생성

---

InitNext() 함수의 알고리즘을 확인하겠습니다.

void InitNext(char *p) {
    int i, j, M = strlen(p);
    next[0] = -1;

    for (i = 0, j = -1; i < M; i++, j++) { // for((1); (2); (6))
        next[i] = j; // (3)
        while((j >= 0) &&(p[i] != p[j])) // (4)
            j = next[j]; // (5)
    }
}

"10100111" 이라는 숫자 배열이 패턴으로 주어졌다고 하면, InitNext 함수는 이 패턴을 인자로 받습니다.

M은 문자열 p의 길이이므로 M = 8을 구할 수 있겠네요.

그러고선 새로운 배열인 next[0]에 -1을 저장합니다. 일단 그렇다고 치죠.

이제 for문을 진행합니다. 이번에도 번호를 따라가며 차근차근 살펴보겠습니다.

 

①번 까지의 상태입니다. next[0]=-1이 저장되고, for루프에 진입하여 i=0, j=-1로 시작합니다.

③ next[0]에 j의 값인 -1을 저장합니다. 바로 윗 단계에서 했던 거네요.

④ 그러고는 j ≥ 0 과 p[i] ≠ p[j] 를 만족하지 않을 때 까지 ⑤ j에 next[j]값을 저장합니다.

그런데 j가 -1 이므로 while문의 조건에 맞지 않으니 그대로 넘어갑니다.

⑥ 마지막으로 i++, j++를 하며 한 루프를 끝냅니다. i=1, j=0이 되네요.

다음 루프를 진행하겠습니다. i=1, j=0인 상태에서 ③ next[1]=0 을 저장해줍니다.

④ j ≥ 0 과 p[i] ≠ p[j] 를 만족하지 않을 때 까지 ⑤ j에 next[j]값을 저장합니다.

j=0 이므로 다음 조건인 p[i]와 p[j]를 비교해야겠네요. 그렇다면 p는 자기 자신을 비교한다는 소리입니다.

p[i] ≠ p[j] 이므로 ⑤ j에는 next[j]가 저장되어 -1이 됩니다.

이젠 j ≥ 0 조건에 부합하지 않으니 ⑥ i++, j++를 하며 새 루프를 돕니다. i=2, j=0이 됩니다.

다음 루프를 확인하겠습니다. ③ next[2]=0을 저장하고, ④ j ≥ 0 이므로 p[i]와 p[j]를 비교합니다.

이번에는 p[i] = p[j] 이므로 while문의 조건에 부합하지 않으니 그대로 지나가서 ⑥ i++, j++를 해줍니다

i=3, j=1의 루프를 돕니다. ③ 먼저 next[3]=1을 저장해 줍니다.

④ 이번에도 방금과 같이 j ≥ 0 조건을 만족하지만 p[i] = p[j] 이므로 ⑥ i++, j++를 하고 다음 루프를 돕니다.

③ next[4]=2를 저장하고, ④ j ≥ 0 이라서 p[4]와 p[2]를 비교하려는데 드디어 서로 다른 값이 나옵니다.

⑤ 신나게 j에 next[j]값을 저장해 줍니다.

④ 그랬더니 여전히 j ≥ 0 조건을 만족하므로, p[i]와 p[j]를 비교합니다.

이번에도 p[i] ≠ p[j]를 만족하므로 ⑤ j에 next[j] 값을 저장합니다.

④ j=-1이 되므로 j ≥ 0 조건에 맞지 않아 while문을 끝냅니다. 그러고선 ⑥ i++, j++를 하고 다음 루프를 돕니다.

i=5, j=0인 상태에서 next[5]=0을 저장해주고, p[i]=p[j] 이므로 조건에 맞지 않아 while문을 스킵하고 i++, j++를 합니다.

i=6, j=1인 루프에서 또 next[6]=1을 저장해주고, 조건에 맞으므로 j에 next[j] 값인 0 을 저장합니다.

j ≥ 0 조건을 만족하니 p[6], p[0]을 비교하는데 p[i] ≠ p[j] 조건을 만족하지 않으니 while문을 건너뛰고 i++, j++를 합니다.

j ≥ 0, p[i] ≠ p[j]를 만족하므로 j에 next[j] 값인 0을 저장합니다.

이번엔 p[i] ≠ p[j]를 만족하지 않으니 while문을 건너뜁니다.

그리고 i++, j++를 하면 i=8, j=1이 되는데,

for 루프의 조건 ② i<M 에서 M=8임을 구했고 이 조건에 맞지 않으니 for 루프를 탈출합니다.

그렇게 최종적으로 아래와 같은 next[] 배열을 얻게 되는 것이 InitNext() 함수의 기능입니다.

---

KMP 알고리즘

---

그렇다면 위에서 구한 next[] 배열을 어떻게 사용할까요?

KMP 알고리즘의 코드를 살펴보겠습니다.

int KMP(char *p, char *t) {
    int i, j, M = strlen(p), N = strlen(t);
    InitNext(p);
    for (i = 0, j = 0; j < M && i < N; i++, j++) {
        while((j >= 0) && (t[i] != p[j]))
            j = next[j];
    }
    if (j == M)
        return i - M;
    else
        return i;
}

KMP() 함수에선 일단 패턴 p와 텍스트 t를 문자열 포인터 형식으로 받습니다.

그리고 변수 M, N을 선언하고 p의 길이와 t의 길이를 저장하고 나니, InitNext() 함수를 불러옵니다.

그렇다면 우리는 KMP 함수 내부에서 next[] 배열도 사용할 수 있겠죠.

다음과 같은 텍스트가 주어졌다고 하면 M=8, N=14 가 저장되겠죠.

for 문에 진입하여 i=0, j=0 부터 시작하여 i=N 혹은 j=M일 때 까지 진행하겠습니다.

내부의 while문의 조건에서, 일단 j ≥ 0을 만족하니 t[i] ≠ p[j]가 만족하는지 확인해야겠죠?

t[i] ≠ p[j] 이므로 while문 내부를 진행합니다. j에 next[j]의 값을 저장하라네요.

next[0]=-1 을 j에 저장한다면, j ≥ 0 조건에 맞지 않으므로 while문을 탈출합니다.

i++, j++를 하여 한바퀴를 돌고, i=1, j=0인 상태에서 또 살펴보겠습니다.

이번엔 t[i] = p[j] 이므로 while문을 진행하지 않고 넘어갑니다. i++, j++를 하여 i=2, j=1인 루프를 진행합니다.

이번에도 t[i] = p[j] 라서 넘어가집니다.

지금까지 계속 t와 p를 비교할 때, 같은 문자가 있다면 넘어가는 것을 볼 수 있습니다.

이처럼 KMP 알고리즘은 text에서 패턴과 동일한 문자가 있다면 조건문에서 걸러서 그냥 건너뛰어 버립니다.

그렇다면 넘어가서 불일치를 만나게 되면 어떻게 될까요? i=4, j=3인 루프입니다.

불일치 시 아까 전과 같이 while문 내부를 수행합니다. j에는 next[j] 값인 1이 저장됩니다. i=4, j=1 입니다.

다시 while 루프를 돌기 위해 조건에 맞는지 확인합니다. 

t[4]와 p[1]의 값이 다르므로 또 j에는 next[j] 값을 저장합니다.

이제 i=4, j=0 인 상태에서 t[4]와 p[0]의 값을 비교하면 같으므로, while문을 탈출합니다.

while문을 벗어나 한 바퀴를 돌았으니 i++, j++를 하여 i=5, j=1인 루프가 되었습니다.

t[5] ≠ p[1] 이므로, while 문을 수행하여 j에 next[j] 값인 0을 넣습니다.

t[5]와 p[0]을 비교했더니 동일하므로 while 문을 수행하지 않습니다.

그런데 i=5, j=0 부터 계속해서 t와 p가 동일한 것을 볼 수 있습니다. 

아까의 경우처럼 동일한 문자는 i++, j++를 하며 다 넘어가줍니다.

그렇게 진행하다 보면 i=12, j=7이 되고, i++, j++를 하면 j=8=M이 되므로, for 문에서 탈출하게 됩니다.

for문이 끝났으니 그 다음 코드를 진행해야겠죠. KMP 알고리즘의 코드를 다시 가져오겠습니다.

int KMP(char *p, char *t) {
    int i, j, M = strlen(p), N = strlen(t);
    InitNext(p);
    for (i = 0, j = 0; j < M && i < N; i++, j++) {
        while((j >= 0) && (t[i] != p[j]))
            j = next[j];
    }
    if (j == M)
        return i - M;
    else
        return i;
}

if절을 살펴보니 j==M 이면 i-M을 리턴하고, 그 외에는 i를 리턴합니다.

자세히 말하자면 text 안에서 pattern을 찾아서 p[] 배열이 끝나 for문을 종료했다면(j==M이면) text와 pattern이 겹치기 시작하는 위치(i-M)를 리턴 하고,

text 안에서 pattern을 찾지 못해 t[] 배열이 끝나 for문을 종료했다면(else) 맨 끝(i)을 리턴한다는 의미입니다.

그렇다면 지금 상황에서는 text 안에서 pattern을 찾았기 때문에 i-M = 5를 리턴하겠죠.

이렇게 KMP 알고리즘의 리턴값으로 text에서 pattern이 시작되는 위치를 얻을 수 있습니다.

---

그런데 만일, 위와 같이 text 내에 pattern이 여러 개 있는 경우에 main 함수에서 그냥 KMP만 불러온다면 패턴이 처음 겹치는 위치인 5만 리턴받고 그 뒤에 있는 text는 무시해 버릴 겁니다.

그러한 경우에, 반복문을 사용하여 KMP를 text가 끝날 때까지 돌리면 해결됩니다.

int M, N, pos;
int previous = 0, i = 0;

M = strlen(pattern);
N = strlen(text);

while (1) {
        pos = KMP(pattern, text + i); // 패턴이 나타난 현재 위치
        pos += previous;
        i = pos + M;

        if (i <= N)
            cout << "패턴이 발생한 위치: " << pos << endl;
        else
            break;

        previous = i;
}

while(1)은 무한 반복문이며, break을 만나면 루프에서 탈출합니다.

while문 내부를 살펴보면, 일단 KMP의 리턴값을 pos라는 변수에 저장해줍니다. pos = 5가 저장되네요.

그러고선 previous 변수의 값을 pos에 더해주는데, 처음에 previous의 값을 0이라 했으니 그대로 진행합니다.

i 에는 pos+M을 저장해주는데, 여기서 pos+M은 text에서 pattern이 끝난 바로 다음 위치입니다.

if절의 조건을 보니 i ≤ N일 때 pos의 값을 출력하는 출력문을 실행하고, i > N이라면 break를 하여 while문을 빠져나옵니다.

이 의미는, text가 끝났다면 while문을 빠져나오라는 의미라고 해석할 수 있습니다.

지금은 i=13 이므로 N=23 보다 작아 pos의 값을 출력하고 계속 루프를 진행합니다.

마지막으로 previous에 i의 값인 13이 저장되며 첫 루프가 끝이 납니다.

 

다음 루프에서도 pos에 KMP의 리턴값을 저장하는데, 이 때 KMP의 인자로 (pattern, text+i) 가 들어감을 볼 수 있습니다.

아까 KMP 함수와 InitNext 함수를 소개할 때, 인자로 "포인터"를 받는다고 말씀드렸습니다.

따라서 text+i는 text[0]의 주소 + i 이므로, text[i]의 주소임을 확인할 수 있죠. 

KMP(pattern, text+i) 의 의미는 결국, text의 i번째 자리부터 다시 KMP 알고리즘을 진행한다는 뜻입니다.

그렇게 되면 pos에는 1이 저장되는데, previous에 13이 저장되어 있으므로 pos+=previous에 의하여 pos = 14가 됩니다.

i = pos+M 이므로 22가 저장되네요. 출력문을 진행하고 previous에 i의 값인 22를 저장하며 다시 한 바퀴를 돕니다.

 

다시 KMP를 진행하면 text가 pattern보다 일찍 끝나므로 (text 안에 pattern이 없으므로) 0을 리턴 받습니다.

pos엔 0이 저장되었다가, pos+=previous에 의하여 pos = 22가 됩니다.

이 때 i = pos+M = 30 이므로, N보다 커지기 때문에 break를 하여 반복문을 빠져나옵니다.

 

이에 따른 최종 출력 결과는 다음과 같습니다.

패턴이 발생한 위치: 5
패턴이 발생한 위치: 14

---

개선된 유한 상태 장치

---

 

void InitNext(char *p) {
    int i, j, M = strlen(p);
    next[0] = -1;

    for (i = 0, j = -1; i < M; i++, j++) {
        next[i] = (p[i] == p[j]) ? next[j] : j;
        while((j >= 0) &&(p[i] != p[j]))
            j = next[j];
    }
}

위의 코드처럼 InitNext 함수를 수정하여 개선된 KMP 알고리즘을 진행할 수 있습니다.

달라진 점은 next[i] = j 에서 next[i] = (p[i] == p[j]) ? next[j] : j 로 바뀐 것 뿐입니다.

이 구문의 의미는, (p[i] == p[j])가 참이면 next[i] = next[j], 거짓이라면 next[i] = j를 저장한다는 것입니다.

 

앞서 확인한 next 배열을 간소화해 보겠습니다.

p[0] == p[2] == p[5] 이며, p[1] == p[3] 입니다. 이러한 경우에는 아래와 같이 next 배열을 간소화할 수 있습니다.

이렇게 next 배열을 간소화하기 위하여 그린 옆의 장치를 개선된 유한 상태 장치라고 합니다.

새로 얻은 next 배열로 진행한 KMP 알고리즘의 시간 복잡도는 O(M+N) 입니다.

 

<틀린 점이 있다면 지적 부탁드립니다. 감사합니다.>