[백준 1786] 찾기 C++

1786번: 찾기

KMP

---

어젯밤부터 이해하는데 어려움을 느꼈던 알고리즘

 

기본 kmp문제를 보니 대놓고 알고리즘을 설명해주고 있다.

워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자.

두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할 수 있다. 이때의 P는 패턴이라고 부르고 T는 텍스트라고 부른다.

편의상 T의 길이를 n, P의 길이를 m이라고 하자. 일반적으로, n ≥ m이라고 가정해도 무리가 없다.  n<m이면 어차피 P는 T중간에 나타날 수 없기 때문이다. 또, T의 i번째 문자를 T[i]라고 표현하도록 하자. 그러면 물론, P의 i번째 문자는 P[i]라고 표현된다.

문자열 P가 문자열 T 중간에 나타난다는 것, 즉 문자열 P가 문자열 T와 매칭을 이룬다는 것이 어떤 것인지 위와 아래의 두 예를 통해 알아보자. 위의 예에서 P는, T의 1번 문자에서 시작하는 매칭에 실패했다. T의 7번 문자 T[7]과, P의 7번 문자 P[7]이 서로 다르기 때문이다.

그러나 아래의 예에서 P는, T의 5번 문자에서 시작하는 매칭에 성공했다. T의 5～11번 문자와 P의 1～7번 문자가 서로 하나씩 대응되기 때문이다.

가장 단순한 방법으로, 존재하는 모든 매칭을 확인한다면, 시간복잡도가 어떻게 될까? T의 1번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 1～m번 문자와 P의 1～m번 문자를 비교한다면 최대 m번의 연산이 필요하다. 이 비교들이 끝난 후, T의 2번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 2～m+1번 문자와 P의 1～m번 문자를 비교한다면 다시 최대 m번의 연산이 수행된다. 매칭은 T의 n-m+1번 문자에서까지 시작할 수 있으므로, 이러한 방식으로 진행한다면 O( (n-m+1) × m ) = O(nm) 의 시간복잡도를 갖는 알고리즘이 된다.

더 좋은 방법은 없을까? 물론 있다. 위에 제시된 예에서, T[7] ≠ P[7] 이므로 T의 1번 문자에서 시작하는 매칭이 실패임을 알게 된 순간으로 돌아가자. 이때 우리는 매칭이 실패라는 사실에서, T[7] ≠ P[7] 라는 정보만을 얻은 것이 아니다. 오히려 i=1…6에 대해 T[i] = P[i] 라고 하는 귀중한 정보를 얻지 않았는가? 이 정보를 십분 활용하면, O(n)의 시간복잡도 내에 문자열 매칭 문제를 풀어내는 알고리즘을 설계할 수 있다.

P 내부에 존재하는 문자열의 반복에 주목하자. P에서 1, 2번 문자 A, B는 5, 6번 문자로 반복되어 나타난다. 또, T의 1번 문자에서 시작하는 매칭이 7번 문자에서야 실패했으므로 T의 5, 6번 문자도 A, B이다.

따라서 T의 1번 문자에서 시작하는 매칭이 실패한 이후, 그 다음으로 가능한 매칭은 T의 5번 문자에서 시작하는 매칭임을 알 수 있다! 더불어, T의 5～6번 문자는 P의 1～2번 문자와 비교하지 않아도, 서로 같다는 것을 이미 알고 있다! 그러므로 이제는 T의 7번 문자와 P의 3번 문자부터 비교해 나가면 된다.

이제 이 방법을 일반화 해 보자. T의 i번 문자에서 시작하는 매칭을 검사하던 중 T[i+j-1] ≠ P[j]임을 발견했다고 하자. 이렇게 P의 j번 문자에서 매칭이 실패한 경우, P[1…k] = P[j-k…j-1]을 만족하는 최대의 k(≠j-1)에 대해 T의 i+j-1번 문자와 P의 k+1번 문자부터 비교를 계속해 나가면 된다.

이 최대의 k를 j에 대한 함수라고 생각하고, 1～m까지의 각 j값에 대해 최대의 k를 미리 계산해 놓으면 편리할 것이다. 이를 전처리 과정이라고 부르며, O(m)에 완료할 수 있다.

 

전처리 과정을 통해 현재 보고있는 pattern의 문자가 접두사의 몇 번째인지 미리 알 수 있게 한다는게 대단하다

 

 

 

 

 

preset(), KMP()함수의 while문 내부의 j = table [j-1]을 이해하는데 시간이 좀 걸렸다.

patten [j]와 text[i]가 달라서 매칭이 실패한 경우 j를 0으로 초기화해줄 필요가 없다.

pattern의 j-1번 문자가 접두사의 몇 번째 문자인지 알 수 있다면 table[해당 문자의 인덱스] 부터 탐색을 시작하면 될 것이다.

그림의 인덱스가 1부터인데 저는 -1씩 해주고 생각했습니다

 

위 그림에서 6번째에서 틀렸기 때문에 j는 바로 직전 문자인 B의 index(5)를 가지고 table을 참조하게된다.

아마도 참조한 table[5]의 값은 2가 나올 것이다.

왜냐하면 preset table을 구하는 과정에서 접두사 AB(4, 5번)가 연속으로 나오기 때문에 table[5]에는 2가 들어갈 것이다. (table[4] = 1이 될 것임)

그래서 매칭이 실패한다면 지금까지 동일했던 접두사의 크기만큼 점프하고 바로 그다음부터 탐색을 다시 하게 된다.

 

 

말로 설명하기 매우 힘든 알고리즘이다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
string text, pattern;
vector<int> table;
vector<int> idxans;
int anscnt = 0;
 
void input(){
    getline(cin, text);
    getline(cin, pattern);
}
 
void preset(){
    table.resize(pattern.size(), 0);
    int j = 0;
    for(int i = 1; i < pattern.size(); i++){
        while(j > 0 && pattern[i] != pattern[j]){
            j = table[j-1];
        }
        if(pattern[i] == pattern[j]){
            table[i] = ++j;
        }
    }
}
 
void KMP(){
    int j = 0;
    for(int i = 0; i < text.size(); i++){
        while(j > 0 && text[i] != pattern[j]){
            j = table[j-1];
        }
        if(text[i] == pattern[j]){
            if(j == pattern.size()-1){
                idxans.push_back(i - pattern.size() + 2);
                anscnt++;
                j = table[j];
            }
            else{
                j++;
            }
        }
    }
}
 
void solve(){
    preset();
    KMP();
    
    cout << anscnt << "\n";
    for(auto &w : idxans){
        cout << w << " ";
    }
}
 
int main(){
    input();
    solve();
    
    return 0;
}