백준 9253번: 스페셜 저지 (C++)

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

9253번: 스페셜 저지

---

Solved By: KMP

 

3번째로 주어지는 문자열이 pattern이라고 하면, pattern이 a와 b에 존재하는지 KMP를 통해 확인할 수 있습니다.

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

vector<int> getPi(string p){
    vector<int> pi(p.size(), 0);
    for(int i = 1, j = 0; i < p.size(); i++){
        while(j > 0 && p[i] != p[j]) j = pi[j - 1];
        if(p[i] == p[j]) pi[i] = ++j;
    }
    
    return pi;
}

bool kmp(string s, string p){
    bool flag = 0;
    auto pi = getPi(p);
    for(int i = 0, j = 0; i < s.size(); i++){
        while(j > 0 && s[i] != p[j]) j = pi[j - 1];
        if(s[i] == p[j]){
            if(j == p.size() - 1){
                return 1;
            }
            else j++;
        }
    }
    
    return 0;
}

int main(){
    string a, b, s;
    cin >> a >> b >> s;
    if(kmp(a, s) && kmp(b, s)) cout << "YES";
    else cout << "NO";
    
    return 0;
}