문자열 - KMP 알고리즘

* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 20장 문자열에 나온 내용을 바탕으로 작성하였습니다.

 

개요 

'문자열'은 간단한 문제여도 쉽지 않은 문제들이 많다.

C++의 <string> STL을 사용하며 많은 부분에서 편리함이 생겼지만, 그럼에도 문자열 문제들은 많은 시간이 소요된다.

하지만 문자열 문제는 카카오 코딩테스트 문제 유형에도 자주 나오며 그 외 많은 문제에서 찾아볼 수 있다.

항상 나를 괴롭혀 왔던 '문자열'에 대해 자세히 공부해 보고자 한다.

 

1. 문자열 검색

문자열을 검색하는 알고리즘에 대해 공부해보자

 

주어진 긴 '짚더미(Haystack)' 문자열 H가 '바늘(Needle)' 문자열 N을 부분 문자열로 포함하는지를 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제를 문자열 검색 문제라 한다.

 

쉽게 말해 H, N이라는 두 개의 문자열을 주고 H에 N이 포함되어 있는지 알아보는 문제이다.

 

대부분, 가장 쉬운 방법은 index 하나하나 비교하는 알고리즘이다.

 

알고리즘은 다음과 같다.

처음으로 H[0] 과 N[0]를 비교한다.

이때 만약 H[0]==N[0] 라면 N의 모든 문자열을 차례대로 H와 비교한다.

만약 틀린 부분이 있다면 break 하고 다시 H[1]과 N[0]을 비교할 것이고, N의 모든 index가 H에 속하고 있다면 저장한다.

코드로도 쉽게 표현할 수 있다.

 

string H, N;
vector<int>ans;
for (int i = 0; i + N.size() <= H.size(); i++) {
    bool flag = true;
    if (H[i] == N[0]) {
        for (int j = 0; j < N.size(); j++) {
            if (H[i + j] != N[j]) {
                flag = false;
                break;
            }
        }
    }
    if (flag == true) ans.push_back(i);
}

 

책의 코드는 모든 index에서 무조건 N과 H가 같지 않을 때까지 비교하는 코드이지만 나는 H[i]==N[0]일때만 탐색하는 코드로 바꿔 보았다. (결국은 똑같다.)

H의 모든 index를 돌며 N[0]와 같을 때만 부분 문자열인지 비교해 보며 맞다면 ans에 저장한다.

 

이 알고리즘은 매우 간단하지만 단점이 있다.

바로 시간복잡도이다. 최악의 경우를 살펴보자.

일단 모든 H의 index에서 탐색하므로 O(|H|) 이고  -> 이때 |H|는 H의 길이(H.size())

만약 조건을 계속 만족한다면 N의 길이만큼 탐색하므로 O(|N|)

즉 최악의 경우 O(|H|*|N|)의 시간복잡도를 가지게 된다.

 

이는 매우 긴 문자열이 입력으로 들어올 때(H나 N의 사이즈가 클 때)는 비효율적이지만, 구현이 간단하다는 장점이 있어서 표준 라이브러리 구현에 많이 사용된다고 한다.

(Ex. C++ <string>의 string::find(), Java 문자열의 indexOf() 등)

 

 

KMP 알고리즘

일반적인 문자열 탐색 알고리즘은 O(|H|*|N|)의 시간복잡도를 가지기 때문에 비효율적이다.

그렇다면 더 빠르게 탐색할 수 있는 방법은 없을까? 하다 나온 알고리즘이 KMP알고리즘이다.

 

먼저 KMP알고리즘을 이해하려면 접두사와 접미사의 개념을 알아야 한다.

예를 들어 문자열 H를 aabbccbdda 라 하자.

이때 접두사는 a, aa, aab, aabb, aabbc,... aabbccbdda라 할 수 있고,

접미사는 a, da, dda, bdda, ..., aabbccbdda라 할 수 있다.

 

이제 접두사와 접미사를 이해했다면 KMP알고리즘을 이해할 수 있다.

왜냐하면 접두사와 접미사를 비교하면 문자열을 탐색할 때 건너뛸 수 있는 부분이 있다는 것을 발견할 수 있다.

나도 처음에는 이해가 안되서 뭐지..? 하며 한참 책을 쳐다봤었다.

결국 실제 예를 들어서 비교해보다가 이해가 되었다.

 

아래 그림을 보자.

 

회색의 네모들이 같은 문자열이라고 생각해 봤을 때, A와 B는 같은 문자열이다. (당연한 이야기)

이때 i+k에서 시작했을 때, 답이 될 수 있으려면 B와 C는 같아야 한다. 

( 요 부분이 내 생각엔 가장 중요한 의미이다.

 B와 C가 같아야만 i+k일 때 정답일 "가능성"이 있다는 이야기이다.)

그렇다면 A=B이고 B=C 이므로 A=C임을 어렵지 않게 알 수 있다.

 

이게 뭐가 중요하지?라고 처음엔 생각했지만 생각을 바꿔봐야 한다.

위에서 가능성이라고 이야기했는데, 다시 말하면 '가능성이 없다면, 굳이 실행하지 않고 건너뛰어도 된다'는 것이다.

 

이렇게 가능성이 없다면 아예 실행하지 않고 건너뛰기 때문에 시간 복잡도가 작아진다.

 

그렇다면 어떤 조건일 때 건너뛸 것인가?

이때 A=C 가 사용된다.

N과 H가 일치하는 문자열만큼을 X라 하면, X의 접미사(A)와 접두사(C)가 같아야 한다는 것이다.

즉, 문자열 X 중 접두사와 접미사가 일치하는 구간을 알아야 한다는 것이다.

(접두사이면서 접미사인 최대 문자열의 길이 만큼이 A, C 가 된다는 것이다.)

 

접두사이면서 접미사인 최대 문자열의 길이를 pi란 배열로 미리 구해 놓아 보자. (길이임을 명심하자!)

 

문자열을 aabaabac 라 하면,

i=0   -> a            -> 0 (없음)

i=1   -> aa           -> 1 (a)

i=2   -> aab         -> 0 (없음)

i=3   -> aaba        -> 1 (a)

i=4   -> aabaa      -> 2 (aa)

...

 

int pi [8] = { 0, 1, 0, 1, 2, 3, 4, 0 } 임을 구할 수 있다.

 

이렇게 미리 pi배열을 구해 놓았다면, 드디어 KMP알고리즘을 완성시킬 수 있다.

 

KMP 알고리즘 코드는 아래와 같다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
vector<int>getPartialMatch(string n) {};
 
//긴 문자열 H의 부분문자열로 N이 출현하는 시작 위치들을 모두 반환하는 함수
vector<int> KMP_search(const string& H, const string& N) {
    int n = H.size(), m = N.size();
    //ans는 일치하는 시작점들을 저장해놓는 배열이다.
    vector<int> ans;
    //pi는 getPartialMatch(N)으로 생성한다 가정하자.
    vector<int>pi = getPartialMatch(N);
    int begin = 0, matched = 0;
    while (begin <= n - m) {
        //만약 긴 문자열의 해당 글자가 바늘의 해당글자와 같다면 matched++(이 때 matched는 긴 문자열과 일치하는 길이)
        if (matched < m && H[begin + matched] == N[matched]) {
            ++matched;
            if (matched == m) ans.push_back(begin);
        }
        else {
            //예외 : matched가 0인 경우에는 다음 칸에서부터 계속
            if (matched == 0) {
                ++begin;
            }
            else {
                begin += matched - pi[matched - 1];
                //begin을 옮겼다고 처음부터 다시 비교할 필요가 없음.
                //즉, i+k로 옮겼을 때, k만큼은 일치함을 알고 있으므로 굳이 비교하지 않는다.
                matched = pi[matched - 1];
            }
        }
    }
    return ans;
}
 

 

이렇게 KMP 알고리즘을 알아보았다.

이 코드에서 추가적으로 알아봐야 할 부분이 pi [] 배열을 생성하는 코드이다.

코드에서 나온 대로 getPartialMatch() 함수를 구현해 보자.

 

말 그대로 접두사와 접미사가 같은 부분 문자열의 최장 길이를 구하면 된다.

대부분 단순하게 하나씩 비교해가며 구하면 될 거 같아요!라고 말하겠지만 똑똑한 사람들은 달랐다.

이 코드 역시 KMP 알고리즘을 사용하면 시간을 단축할 수 있다.

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
vector<int>getPartialMatch(const string& N) {
    //N에서 자기 자신을 찾으면서 나타나는 부분 일치를 이용해 pi를 계산한다.
    int m = N.size();
    vector<int>pi(m, 0);  //길이를 m만큼, 0으로 초기화
    //KMP로 자기 자신을 찾는다.
    //N을 N에서 찾는다. begin=0 이면 자기 자신을 찾으므로 안됨! -> a 같이 길이가 1이면 최장 길이는 0이다.
    int begin = 1, matched = 0;
    //비교할 문자가 N의 끝에 도달할 때까지 찾으면서 부분 일치를 모두 기록한다.
    while (begin + matched < m) {
        if (N[begin + matched] == N[matched]) {
            ++matched;
            pi[begin + matched - 1] = matched;
        }
        else {
            if (matched == 0) {
                ++begin;
            }
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return pi;
}

 

문제 1. 접두사/접미사 (문제 ID : NAMING)

https://algospot.com/judge/problem/read/NAMING

algospot.com :: NAMING

문제에서 원하는 답은 입력받은 문자열 S의 접두사=접미사인 문자열의 길이이다.

이 때 pi 배열에는 문자열의 길이가 k일 때, 접두사=접미사인 문자열의 최장 길이가 몇인지 저장되어 있다.

 

처음에는 책을 봐도 이해가 안 됐다. 한참을 봐도 뭐지.... 생각했는데 번뜩 이해가 됐다.

 

예를 들어보자. S= aabcaa 라 하자. 그럼 k=5(S의 길이) 일 때, 접두사=접미사 인 문자열의 최장 길이는 pi [5-1] = 2, 즉 aa 임을 알 수 있다. 여기서 우리가 해야 할 일은 다시 모든 문자열을 탐색하는 게 아니다."aa", 즉 k=2일 때를 탐색해야 한다. 왜냐하면 aa가 S의 최장 길이 접두사=접미사인 문자열이므로 또다시 aa에서 접두사=접미사인 문자열만 탐색하면 된다.

 

코드로 짜면 k=pi[k-1] 이다.

처음에는 이 부분이 이해가 안 됐었다.

왜?? k가 pi[k-1]이 돼야 하지? 다른 길이의 문자열은 답이 안 되는 걸까?

사실 당연한 이야기이다. 

 

pi는 S의 길이가 1,2,3,... k(최대) 일 때의 모든 부분 문자열의 최장 길이를 가지고 있는 배열이다.

하지만 이 문제는 S의 모든 길이에서의 모든 부분 문자열을 구하는 것이 아니다.

길이가 S 일 때의 부분 문자열을 구하는 문제이다. 

 

즉 S의 최장길이 접두사=접미사인 문자열을 구하고, 구한 그 문자열의 최장 길이 접두사=접미사인 문자열을 구하고........ 이렇게 반복해서 구하는 것이다.

 

코드는 아래와 같다. pi배열 구하는 코드는 위의 코드와 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
vector<int>getPartialMatch(const string& N) {
    //N에서 자기 자신을 찾으면서 나타나는 부분 일치를 이용해 pi를 계산한다.
    int m = N.size();
    vector<int>pi(m, 0);  //길이를 m만큼, 0으로 초기화
    //KMP로 자기 자신을 찾는다.
    //N을 N에서 찾는다. begin=0 이면 자기 자신을 찾으므로 안됨! -> a 같이 길이가 1이면 최장 길이는 0이다.
    int begin = 1, matched = 0;
    //비교할 문자가 N의 끝에 도달할 때까지 찾으면서 부분 일치를 모두 기록한다.
    while (begin + matched < m) {
        if (N[begin + matched] == N[matched]) {
            ++matched;
            pi[begin + matched - 1] = matched;
        }
        else {
            if (matched == 0) {
                ++begin;
            }
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return pi;
}
 
int main() {
    string a, b;
    cin >> a >> b;
    string temp = a + b;
    vector<int>ans, pi = getPartialMatch(temp);
    int k = temp.size();
    while (k > 0) {
        //k, 즉 입력받은 문자열도 이름 가능
        ans.push_back(k);
        k = pi[k - 1];
    }
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
}

 

문제 2. 팰린드롬 만들기 (문제 ID : PALINDROMIZE)

https://algospot.com/judge/problem/read/PALINDROMIZE

algospot.com :: PALINDROMIZE

이 문제는 앞으로 읽었을 때와 뒤로 읽었을 때가 같은 문자열을 찾는 문제이다.

 

힌트는 문제에 있었다. 바로 "문자열을 뒤집은 뒤 붙이면 항상 팰린드롬이 되므로..."

여기서 해결책은 다음과 같다.

문자열 S를 입력받았을 때, 뒤집어진 문자열 S'을 만든다.

그리고 S'을 KMP알고리즘을 통해 S와 비교하는데 종료 조건을 살짝 바꿔준다.

이 문제는 a의 모든 문자열이 b의 문자열과 일치했을 때 종료한다.

 

위 그림을 보면 쉽게 이해 가능하다.

 

begin=0 일 때, S[0]!=S'[0]이므로 건너뛴다.

(건너뛸 때도 KMP알고리즘을 사용하지만, 설명은 위에서 너무나도 많이 했기 때문에 생략)

begin=1 일 때, S[...3]=S'[...3] 이므로 종료 조건을 만족한다.

 

즉 anon이란 문자열이 있었다면, 팰린드롬을 만들려면 a란 문자열 하나만 더해주면 된다는 이야기이다.

 

코드로 표현하면 아래와 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
vector<int>getPartialMatch(const string& N) {
    //N에서 자기 자신을 찾으면서 나타나는 부분 일치를 이용해 pi를 계산한다.
    int m = N.size();
    vector<int>pi(m, 0);  //길이를 m만큼, 0으로 초기화
    //KMP로 자기 자신을 찾는다.
    //N을 N에서 찾는다. begin=0 이면 자기 자신을 찾으므로 안됨! -> a 같이 길이가 1이면 최장 길이는 0이다.
    int begin = 1, matched = 0;
    //비교할 문자가 N의 끝에 도달할 때까지 찾으면서 부분 일치를 모두 기록한다.
    while (begin + matched < m) {
        if (N[begin + matched] == N[matched]) {
            ++matched;
            pi[begin + matched - 1] = matched;
        }
        else {
            if (matched == 0) {
                ++begin;
            }
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return pi;
}
 
int maxOverlap(const string& a, const string& b) {
    vector<int> pi = getPartialMatch(b);
    int begin = 0, matched = 0;
    int n = a.size(), m = b.size();
    while (begin < n) {
        if (matched < m && a[begin + matched] == b[matched]) {
            ++matched;
            if (begin + matched == n) { //a의 모든 문자열이 b와 일치했을 때, 즉 종료조건
                return n - matched; 
            }
        }
        else {
            if (matched == 0) {
                ++begin;
            }
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return 0;
}
 
int main() {
    string a, b;
    int t;
    cin >> t;
    while (t--) {
        cin >> a;
        string b = a;
        reverse(b.begin(), b.end());
        int x = maxOverlap(a, b);
        cout << x + a.size() << "\n";
    }
}

 

책에는 maxOverlap 함수가 matched(일치하는 길이)를 반환하게 작성되어 있는데,

n-matched를 return 하면 더 좋을 것 같아서 바꿔보았다. (근데 그냥 똑같은 이야기이다ㅋㅋ)

 

문제 3. 재하의 금고 (문제 ID : JAEHASAFE)

https://algospot.com/judge/problem/read/JAEHASAFE

algospot.com :: JAEHASAFE

문제는 옛날 전화기의 다이얼 돌리는 방식처럼 문자열을 "환형 시프트"연산을 통해 구현해 내면 된다.

처음 문제를 봤을 때, 이 문제에 왜 KMP알고리즘이 들어가는 거지?라고 생각했다.

단순한 앞의 문자열을 맨 뒤로 보내주면서 반복하면 되는 알고리즘 아닌가?라고 생각했다.

보통 나 같은 경우는 이런 문제는 deque을 사용해 푸는데 쉽게 풀릴 것 같았다.

 

당연히 틀렸다. 문제는 역시 시간 복잡도였다.

 

문자열의 길이가 최대 10000이라고 하였으므로, 최악의 경우 문자열끼리 비교를 10000의 제곱 번 하게 된다.

당연히 시간 초과..

 

다시 생각해보니 KMP알고리즘은 문자열 탐색을 위한 알고리즘이다.

다이얼 문자열을 현재 문자열과 비교해서 같은지 탐색을 하면 답을 구할 수 있을 것 같았다.

 

그렇다면 문제는

남는 문자열 즉 aabac에 abaca가 있는지 탐색하려면 abac는 존재하지만 나머지 a가 존재하는지를 알아야 한다.

요 남는 문자열을 해결하려면 같은 문자열을 두 번 이어 붙이면 간단하지 않을 까?라고 생각해보았다.

책 역시 같은 풀이 방법을 말하고 있는데, 이의 구현은 KMP알고리즘을 이해하고 있다면 어렵지 않다.

 

문제에서 시계 방향으로 갈 때와 반시계 방향으로 갈 때를 구하라 했으므로 

간단하게 KMP 함수의 매개변수의 순서만 바꿔주면 된다. 

ex) (original + original, temp) -> (temp + temp, original)

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
vector<int>getPartialMatch(const string& N) {
    //N에서 자기 자신을 찾으면서 나타나는 부분 일치를 이용해 pi를 계산한다.
    int m = N.size();
    vector<int>pi(m, 0);  //길이를 m만큼, 0으로 초기화
    //KMP로 자기 자신을 찾는다.
    //N을 N에서 찾는다. begin=0 이면 자기 자신을 찾으므로 안됨! -> a 같이 길이가 1이면 최장 길이는 0이다.
    int begin = 1, matched = 0;
    //비교할 문자가 N의 끝에 도달할 때까지 찾으면서 부분 일치를 모두 기록한다.
    while (begin + matched < m) {
        if (N[begin + matched] == N[matched]) {
            ++matched;
            pi[begin + matched - 1] = matched;
        }
        else {
            if (matched == 0) {
                ++begin;
            }
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return pi;
}
 
int kmpalgo(const string& a, const string& b) { //a가 원래 문자열*2, b가 찾고자 하는 문자열 
    int n = a.size(), m = b.size();
    vector<int> pi = getPartialMatch(b);
    int begin = 0, matched = 0;
    while (begin <= n - m) {
        if (matched < m && a[begin + matched] == b[matched]) {
            ++matched;
            if (matched == m) {
                return begin; //첫 번째로 일치하면 바로 종료 시킨다.
            }
        }
        else {
            if (matched == 0) {
                ++begin;
            }
            else {
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return 0;
}
 
int main() {
    int t, x;
    cin >> t;
    while (t--) {
        cin >> x;
        string original, temp;
        cin >> original;
        int ans = 0;
        for (int i = 1; i <= x; i++) {
            cin >> temp;
            if (i % 2 == 1) { //홀수번째는 시계방향
                ans += kmpalgo(temp + temp, original);
                original = temp; //반드시 original이 temp로 바뀌어야한다 - 돌렸으므로
            } 
            else { 
                ans += kmpalgo(original+original,temp);
                original = temp;
            }//짝수번째는 반 시계방향
        }
        cout << ans << "\n";
    }
}

 

KMP 코드에서 문자열이 같아지는 시작점을 발견하면 바로 함수를 중지하도록 바꿨다.

홀 수 번째 입력에서는 시계방향으로 탐색해야 하므로 함수 인자로 (temp + temp, original)를 주었고,

짝 수 번째 입력에서는 반시계 방향으로 탐색해야 하므로 함수 인자로 (original + original, temp)를 주었다.

이는 직접 해보다 보면 이해하기 쉽다.

 

이로써 KMP알고리즘에 대해 알아보았다.

이 알고리즘을 알고 있다면 앞으로 문자열 탐색 문제는 쉽게 해결할 수 있을 것 같다.