백준 16172번: 나는 친구가 적다 (Large) (C++)

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

16172번: 나는 친구가 적다 (Large)

---

Solved By: KMP

 

주어진 문자열에서 숫자를 제외하고 다시 문자열을 만들어서 패턴과 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){
    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 S; cin >> S;
    string s;
    
    for(int i = 0; i < S.size(); i++){
        if((S[i] >= 'A' && S[i] <= 'Z') || (S[i] >= 'a' && S[i] <= 'z')){
            s += S[i];
        }
    }
    
    string p; cin >> p;
    cout << kmp(s, p);
}