[Platinum 4] 1786 찾기

https://www.acmicpc.net/problem/1786

 

이 문제는 KMP 알고리즘을 사용해서 중복 문자열을 찾는 것이다.

 

KMP알고리즘은 아래 참고

https://hanseongbugi2study.tistory.com/310

[Algorithm] KMP 알고리즘

 

실패함수는 아래 코드와 같다.

void Failure(){
    int j = 0;

    for(int i = 1;i<P.length();i++){
        while(j>0 && P[i] != P[j])
            j = table[j - 1];
        
        if(P[i] == P[j])
            table[i] = ++j;
    }
}

 

실패함수는 패턴의 접두사와 접미사를 비교하여 같은 문자가 있는지 확인하여

테이블에 그 길이를 저장하는 함수이다.

불일치가 발생한 index가 j인 경우, 다음 비교를 위해 탐색 문자열의 위치를 table[j - 1]로 이동한다.

 

KMP 알고리즘은 아래와 같다.

void KMP(){
    int N = T.length();
    int M = P.length();
    Failure();

    int j = 0;
    for(int i = 0;i<N;i++){
        while(j>0 && T[i] != P[j]){
            j = table[j - 1];
        }
        if(T[i] == P[j]){
            if(j == M - 1){
                answer.push_back(i - M + 2);
                j = table[j];
            }
            else{
                j++;
            }
        }
    }
}

 

KMP 알고리즘은 실패함수와 유사한 부분이 있다.

패턴과 Text를 비교하여 같은 경우 해당 인덱스를 저장하면 문자열 매칭에 성공할 수 있다.

이때 j가 M-1과 같을 경우에만 인덱스를 저장하는 이유는

Text와 패턴의 비교가 M - 1까지 진행되어야 모든 문자를 검사한 것이기 때문이다.

인덱스를 저장한 후 j를 현재 table에 해당하는 값으로 변경한다. 이는 다음 비교를 위해서다.

 

#include <iostream>
#include <vector>
using namespace std;

string T, P;
int table[1000001];
vector<int> answer;

void Failure(){
    int j = 0;

    for(int i = 1;i<P.length();i++){
        while(j>0 && P[i] != P[j])
            j = table[j - 1];
        
        if(P[i] == P[j])
            table[i] = ++j;
    }
}

void KMP(){
    int N = T.length();
    int M = P.length();
    Failure();

    int j = 0;
    for(int i = 0;i<N;i++){
        while(j>0 && T[i] != P[j]){
            j = table[j - 1];
        }
        if(T[i] == P[j]){
            if(j == M - 1){
                answer.push_back(i - M + 2);
                j = table[j];
            }
            else{
                j++;
            }
        }
    }
}


int main() {
    getline(cin,T);
    getline(cin, P);
    KMP();
    cout<<answer.size()<<'\n';
    for(int i = 0;i<answer.size();i++)
        cout<<answer[i]<<' ';
}