[백준/C++] 16916번: 부분 문자열(G3)

문제

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

16916번: 부분 문자열

 

 

 

 

사용한 알고리즘

• 2022.01.16 - [PS/Algorithm] - [알고리즘 개념정리] 2. 문자열 (Polynomial Rolling hash)

-> Polynomial Rolling hash 

• KMP

 

 

 

풀이 

방법1. Polynomial Rolling hash 

1. P를 정수 p로 바꿔준다
2. S의 첫번째 부분 문자열을 정수 s으로 바꿔준다.
3. s과 p가 같으면 1을 출력하고 종료한다.
4. S의 모든 부분 문자열을 정수 s으로 바꾸고 p와 비교해준다.

// S보다 P의 길이가 더 긴 경우 예외처리도 해주자

 

방법2. KMP

KMP알고리즘에서 
문자 매칭에 실패했을 때, 얼만큼 건너뛰어야 하는지 알기위해
실패함수 라는 개념을 이용한다.

실패함수의 값은
문자 매칭에 실패하기 직전 상황에서,
접두사/접미사가 일치한 최대 길이이다.

(참고자료 :  https://kbw1101.tistory.com/54)

 

* P와 실패함수 값 예시

ex1)

A	B	C	D	A	B	D
0	0	0	0	1	2	0

만약 문자열 S와 P가 ABCDAB까지 같고 그 다음글자가 S[i]!=p[6]라면 (즉, S[i]!='D')
'B'(=P[5])의 실패함수 값이 2 이므로 P[2]인 'C'부터 S[i]랑 비교시작하면 된다.

ex2)

A	B	A	C	A	B	A	B
0	0	1	0	1	2	3	2

ex3)

A	B	A	B	A	B	A	B
0	0	1	2	3	4	5	6

 

 

 

소스코드

방법1. Polynomial Rolling hash 

#include <iostream>
#include <cstring>

typedef long long ll;
using namespace std;

// Polynomial Rolling hash
#define X 27
// mod 사용 안함

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    string S,P; cin>>S>>P;

    // 에외처리
    if(S.length()<P.length()){
        cout<<0;
        return 0;
    }

    // 1. P를 정수 p로 바꿔준다
    ll p=0;
    ll POW=1;
    for(ll i=P.length()-1; i>=0; i--){
        p += ll(P[i]-'a'+1)*POW;
        POW *= X;
    }

    // 2. S의 첫번째 부분 문자열을 정수 s으로 바꿔준다.
    ll s=0;
    POW=1;
    for(ll i=P.length()-1; i>=0; i--){
        s += ll(S[i]-'a'+1)*POW;
        POW *= X;
    }
    // 3. s과 p가 같으면 1을 출력하고 종료한다.
    if(s==p){
        cout<<1;
        return 0;
    }

    // 4. S의 모든 부분 문자열을 정수 s으로 바꾸고 p와 비교해준다.
    POW /= X;
    for(ll i=0; i<S.length()-P.length(); i++){
        s -= ll(S[i]-'a'+1)*POW;;
        s *= X;
        s += ll(S[i+P.length()]-'a'+1);
        if(s==p){
            cout<<1;
            return 0;
        }
    }
    cout<<0;
    return 0;
}

 

방법2. KMP

#include <iostream>
using namespace std;

int cnt=0;
int fail_function[1000000];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    string s,p; cin>>s>>p;

    // 1. 실패함수를 배열에 채워준다.
    int j=0;
    for(int i=1; i<p.length(); i++){
        while(j>0 && p[i]!=p[j])
            j=fail_function[j-1];
        if(p[i]==p[j]) fail_function[i]= ++j;
    }

    // 2. 실패함수를 이용해 문자열을 비교한다.
    j=0;
    for(int i=0; i<s.length(); i++){
        while(j>0 && s[i]!=p[j])
            j=fail_function[j-1];
        if(s[i]==p[j]) j++;
        if(j>=p.length()){
            cnt++;
            j=fail_function[j-1];
        }
    }

    if(cnt) cout<<1;
    else cout<<0;
    return 0;
}