BOJ 10745 Censoring (Gold)

문제 링크입니다.

10747번 문제를 먼저 풀어 봅시다.

문제 요약

주어진 문자열 $S$에서 $N$개의 패턴 $P_1, P_2, \cdots, P_N$을 앞에서부터 찾는 대로 지워나갑니다. 최종 문자열을 구하세요.

풀이

$S$에서 여러 개의 패턴을 동시에 찾는 건 아호-코라식으로 슥슥하면 됩니다. 찾은 패턴을 $S$에서 날려버린 뒤의 처리만 고민해 보면 됩니다.

아호-코라식은 근본적으로 트리 위에서 KMP를 달리는 것과 다르지 않습니다. 마찬가지로 다음 문자가 틀려먹었을 때 어디까지 돌아가야 되는 지를 실패 함수라고 이름을 붙여서 관리합니다. S를 순회하면서 벌어지는 상태 전이는 여전히 incremental하니 패턴을 찾으면 없던 셈 치고 마저 아호-코라식을 진행하면 됩니다.

10747번 문제에서는 드러나지 않았는데, 단순히 문자열을 뒤로 감는 식으로만 처리하면 직전 문자에서 실패 함수를 따라 어디까지 뒤로 가야 되는 지를 매번 계산하게 되어서 비효율적입니다. 이를 해결하기 위해 각 상태마다 다음 문자가 뭐냐에 따라 실제로 어디까지 되돌아가게 되었는 지를 적당히 저장해 두고 갖다 쓰도록 구현해 줍시다. (아래 코드에서는 FAIL이 해당 기능을 해 줍니다.)

총 시간 복잡도는 ${\cal O}((\vert S \vert + \Sigma \vert P \vert) \lg \Sigma \vert P \vert)$입니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;

struct trienode{
	int child[26], fail, w;
	trienode(){
		w = fail = 0;
		for(int i = 0; i < 26; i++) child[i] = -1;
	}
};

struct Trie{
	vector<trienode> t;
	map<pii, int> FAIL;
	int _newNode(){
		t.push_back(trienode());
		return t.size()-1;
	}
	Trie(){_newNode();}
	int clear(){
		t.clear();
		t.push_back(trienode());
		return t.size()-1;
	}
	void add(string& str, int w = 1){
		int node = 0;
		for(auto& s : str){
			int c = s-'a';
			if(t[node].child[c] == -1) t[node].child[c] = _newNode();
			node = t[node].child[c];
		}
		t[node].w += w;
	}
	void bfs(){
		queue<int> q;
		q.push(0);
		t[0].fail = 0;
		while(q.size()){
			int now = q.front(); q.pop();
			for(int i = 0; i < 26; i++){
				if(t[now].child[i] == -1) continue;
				int nxt = t[now].child[i];
				if(!now) t[nxt].fail = 0;
				else{
					int prev = t[now].fail;
					while(prev && (t[prev].child[i] == -1)) prev = t[prev].fail;
					if(t[prev].child[i] != -1) prev = t[prev].child[i];
					t[nxt].fail = prev;
				}
				q.push(nxt);
				t[nxt].w += t[t[nxt].fail].w;
			}
		}
	}	
	int transit(int now, int c){
		if(FAIL.find({now, c}) != FAIL.end()) return FAIL[{now, c}];
		pii state = {now, c};
		while(now && t[now].child[c] == -1) now = t[now].fail;
		if(t[now].child[c] != -1) return FAIL[state] = t[now].child[c];
		return FAIL[state] = 0;
	}
	void solve(string& str){
		int now = 0;
		vector<char> ans;
		stack<int> rollback;
		rollback.push(0);
		for(auto& c : str){
			ans.push_back(c);
			now = transit(now, c-'a');
			rollback.push(now);
			if(t[now].w){
				for(int i = 0; i < t[now].w; i++){
					rollback.pop(); ans.pop_back();
				}
				now = rollback.top();
			}
		}
		for(auto& c : ans) cout << c;
	}
} trie;

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	string s; cin >> s;
	int n; cin >> n;
	while(n--){string p; cin >> p; trie.add(p, p.size());}
	trie.bfs();
	trie.solve(s);
}