BOJ 10747 Censoring (Silver)

문제 링크입니다.

문제 요약

주어진 문자열 $S$에서 패턴 $P$를 앞에서부터 찾는 대로 지워나갑니다. 최종 문자열을 구하세요.

풀이

$S$에서 $P$를 찾는 건 KMP로 슥슥하면 됩니다. 찾은 패턴을 $S$에서 날려버린 뒤의 처리만 고민해 보면 됩니다.

KMP의 작동 원리는 문자열의 각 글자마다 다음 글자가 패턴이랑 안 맞으면 어디로 날려보낼 지를 계산하면서 incremental하게 진행하는 방식입니다. 뒤쪽 문자열이 갑자기 바뀐다고 해서 앞쪽의 이미 구해둔 이 값들이 바뀔 일은 없기 때문에, KMP를 돌리다가 패턴을 찾으면 그 패턴을 애초에 없던 것처럼 취급하고 그 전 문자에서 값을 끌어와서 마저 KMP를 진행하면 됩니다. 총 시간 복잡도는 ${\cal O}(\vert S \vert + \vert P \vert)$입니다.

코드

#include<bits/stdc++.h>
using namespace std;
deque<char> st;
stack<int> ex;
vector<int> ff;

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

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	string s, explode; cin >> s >> explode;
	ff = Failure_Function(explode);
	ex.push(0);
	for(int i = 0; i < s.length(); i++){
		st.push_back(s[i]);
		int now = ex.top();
		while(now){
			if(explode[now] == s[i]){
				ex.push(now+1);
				break;
			}
			now = ff[now-1];
		}
		if(!now) ex.push(explode[0] == s[i]);
		if(ex.top() == explode.length()){
			for(int e = 0; e < explode.length(); e++){
				ex.pop();
				st.pop_back();
			}
		}
	}
	while(!st.empty()){
		cout << st.front();
		st.pop_front();
	}
}