[C++] 백준 16916번 - 부분 문자열 (KMP 알고리즘, Failure Function)

문제 링크 : https://www.acmicpc.net/problem/16916

16916번: 부분 문자열

 

문제

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

입력

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

출력

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

 

---

 

 

접근방법

처음에는 문자열의 각 인덱스에 대해서 substr()를 호출해서 검사했는데, 시간초과가 났다.

그래서 KMP알고리즘을 이용하였다.

 

KMP 알고리즘을 사용하기 위해서는 주어진 문자열에 대해 먼저 Failure Function을 구해야한다.

 

*Failure Function 이란? 

  - KMP 알고리즘에서 mismatch 발생 시, 다음번에 비교해야 할 Pattern 상의 위치를 알려주는 함수.

  - Failure Function F(j) : index[0] ~ index[j] 까지 proper prefix와 proper suffix가 매치되는 최대 길이를 저장한다.

 

 

먼저 왼쪽 그림을 보면 쉽게 이해할 수 있다.

 

1) j = 5 에서 mismatch가 발생했다.

2) F[j-1] = F[4]를 확인한다. 

3) F[4] = 2 이므로 index = 0과 1에 해당하는 앞의 두 문자("ab"는 검사할 필요 없이 스킵한다.)

4)  index = 2 부터 재탐색한다.

 

 

 

* F[4] = 2 라는 것은 가장 길게 match 되는 p.p와 p.s 길이를 의미하기도 하지만, 다음 스텝에서 비교해야할 pattern의 index를 의미하기도 한다. 

 

Failure Function을 구하는 코드는 아래와 같다.

void FailFunc(string pattern){
	int len = pattern.length();
    int j = 0;
	vector<int> failVec(len, 0);	//0번 인덱스는 무조건 0
    
    for(int i = 1; i<len; i++){
    	while(j>0 && pattern[i] != pattern[j]){		//j = 0이거나 mismatch 발생하면 -> 비교 시작 지점(j) 위치 조정. 
		j = failVec[j-1];
        }
        
        if(pattern[i] == pattern[j]) failVec[i] = ++j;		//일치하면 계속 i와 j 증가시켜나감.
    }
}

 

이제 위의 코드에 따라 차근차근 "abaaba"의 Failure Function을 구해보자.

 

i	0	1	2	3	4	5
Pattern	a	b	a	a	b	a
Failure Func	0	0	1	1	2	3

step 1) i = 1, j = 0에서 시작한다.

step 2) i = 1, j = 0 -> mismatch -> i++ (아직 j가 0 이므로 i만 증가)

step 3) i = 2, j = 0 -> match -> i++, ++j  -> F[2] = 1

step 4) i = 3, j = 1 -> mismatch -> j = F[1-1] = F[0] = 0

step 5) i = 3, j = 0 -> match -> F[i] = ++j -> F[3] = 1

step 6) i = 4, j = 1 -> match -> F[i] = ++j -> F[4] = 2

step 7) i = 5, j = 2 -> match -> F[i] = ++j -> F[5] = 3

 

 

 

이제 Failure Function을 이용해서 KMP알고리즘으로 전체 문자열에서 주어진 부분 문자열을 찾을 수 있는지 검사해보자.

 

 

수도코드는 위와 같다. Failure Function을 구하는 알고리즘과 유사하다.

match가 되었을 때, pattern을 가리키는 j가 문자열의 끝을 가리키고 있으면 부분 문자열을 찾은것이다! 

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

 

bool KMP(string S, string P){
	vector<int> failVec = FailFunc(string P);
    int j = 0;
    for(int i = 0; i<S.length(); i++){
    	while(j>0 && S[i] != P[j]){					//mismatch면 Failure Function 참고
    		j = failVec[j-1];
    	}
        
    	if(S[i] == P[j]){
        	if(j == P.length() -1) return true;		//match인데 끝까지 검사한거면 
            else j+=1;								//아직 끝까지 검사 안 했으면 j 증가
        }
    }
   return false;
}

 

 

 

구현 코드

//
//  문자열_BOJ16916_부분문자열.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/09.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int N;

vector<int> failFunc(string P){
    int plen = (int)P.length();
    vector<int> failVec(plen, 0);
    int j = 0;
    for(int i = 1; i<plen; i++){
        while(j>0 && P[i]!=P[j]){
            j = failVec[j-1];
        }
        if(P[i] == P[j]){
            failVec[i] = ++j;
        }
    }
    return failVec;
}

int KMP(string S, string P){
    vector<int> failVec = failFunc(P);
    int j = 0;
    
    for(int i = 0; i<S.length(); i++){      //S 길이 기준
        while(j>0 && S[i] != P[j]){
            j = failVec[j-1];
        }
        if(S[i] == P[j]){
            if(j== P.length()-1) return 1;      //P 길이 기준
            else j+=1;
        }
    }
    return 0;
    
}

int main(){
    
    string S, P;
    cin >> S >> P;
 
    N = (int)S.length();
    
    cout << KMP(S, P);

    return 0;
}