BOJ 10747 - Censoring 링크
(2023.08.30 기준 P4)

문제

문자열 S, T가 주어진다. 만약에 S 안에 T를 발견한다면, 그 부분을 지우고 남은 부분을 다시 붙인다. 이 작업을 T가 발견되지 않을 때까지 반복하여 남는 문자열 출력

알고리즘

KMP 응용

풀이

가장 먼저 떠올릴 수 있는 풀이는 'KMP를 T가 발견되지 않을 때까지 반복'이다. 하지만 최악의 경우 O(|S|²) 이므로 불가능하다.

KMP는 실패 함수를 구해놓고, 필요하지 않은 계산은 효율적으로 건너뛰어 시간 복잡도를 엄청 줄인 문자열 탐색 알고리즘이다. 만약, 문자열을 다 찾았다면? 다시 다음 문자열을 찾기 위해 현재 단계가 실패 함수 값을 따라 조정됨을 알 수 있다. 이를 어떻게 응용하면 뭔가 할 수 있을 것 같다.

예제를 살펴보자.
moo를 찾으면 지워서 직전 o에서 다시 시작해야 한다. 이 때, 만약에 저장되어 있던 단계를 꺼내쓰면 어떨까?

KMP를 진행하면서 나오는 단계를 길이마다 저장해두자. 그리고 스택에 검사하는 문자열 하나하나를 쌓으면서, 그대로 똑같이 KMP를 진행하자.
만약에 T를 찾았다면? T의 길이만큼 스택에서 pop하자. 그리고 남은 스택의 길이에 따른 저장된 단계를 다시 꺼내쓰면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string S, T; cin >> S >> T;

    // T의 실패 함수 구하기
    int t = T.size(), pi[t];
    fill(pi, pi + t, 0);
    for (int i = 0, j = 1; j < t; j++){
        while (i && T[i] != T[j]) i = pi[i - 1];
        if (T[i] == T[j]) pi[j] = ++i;
    }

    // KMP
    vector<char> stk; // 정답이 될 문자 스택
    int dp[S.size() + 1]; // 각 길이마다의 단계 저장
    int i = 0; // 현재 단계
    for (char s: S){
        stk.push_back(s); // 스택에 현재 문자를 쌓는다.
        while (i && T[i] != s) i = pi[i - 1]; // 문자가 일치할 때까지 실패 함수 값을 따라 단계를 조정
        if (T[i] == s){ // 문자가 일치
            if (i == t - 1){ // T의 모든 문자를 찾았다면
                for (int _ = 0; _ < t; _++) stk.pop_back(); // T의 길이만큼 스택에서 빼고
                i = dp[stk.size()]; // 단계는 dp[스택의 길이]로 조정
            }
            else i++; // 아직 T를 모두 찾지 못했다면 단계만 향상
        }
        dp[stk.size()] = i; // 현재 단계를 저장
    }

    for (char s: stk) cout << s;
}

• Python

import sys; input = sys.stdin.readline

S = input().strip()
T = input().strip()

# T의 실패 함수 구하기
t = len(T)
pi = [0] * t
i = 0
for j in range(1, t):
    while i and T[i] != T[j]:
        i = pi[i - 1]
    if T[i] == T[j]:
        i += 1
        pi[j] = i

# KMP
stk = [] # 정답이 될 문자 스택
dp = [0] * (len(S) + 1) # 각 길이마다의 단계 저장
i = 0 # 현재 단계
for s in S:
    stk.append(s) # 스택에 현재 문자를 쌓는다.
    while i and T[i] != s: # 문자가 일치할 때까지 실패 함수 값을 따라 단계를 조정
        i = pi[i - 1]
    if T[i] == s: # 문자가 일치
        if i == t - 1: # T의 모든 문자를 찾았다면
            for _ in range(t): # T의 길이만큼 스택에서 빼고
                stk.pop()
            i = dp[len(stk)] # 단계는 dp[스택의 길이]로 조정
        else: # 아직 T를 모두 찾지 못했다면 단계만 향상
            i += 1
    dp[len(stk)] = i # 현재 단계를 저장

print(*stk, sep = '')