백준 10747 Censoring

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

문자열 S에서 문자열 T를 모두 삭제하는 문제입니다. T를 삭제했는데 연결되어 또 T가 나오는 경우에도 고려해야 하기 때문에 조금 까다롭습니다. 문자열 매칭 에서 KMP를 보고 오는 것도 도움이 될 것 같습니다.

제 풀이는 KMP 알고리즘과 거의 일치하지만, 짚더미에서 일치하는 바늘이 나왔을 때 두 포인터가 갖게 되는 값이 조금 달라집니다. match 포인터의 경우 문자열을 붙여나가다가 바늘이 나오면 바늘을 뽑아내고 뽑아낸 문자열에서 가장 마지막 위치가 가졌었던 match 값으로 update해줍니다. 따라서 우리는 추가적으로 match를 저장하는 배열을 하나 더 만들어 주어야 합니다.

begin포인터의 경우 약간의 꼼수를 사용하였습니다. S[begin+match]와 T[match]를 비교하게 되기 때문에 begin+=(tl-match)를 해준다면 실제로는 begin이 저 위치에 있지 않더라도(즉, 폭파된 위치에 begin이 존재하더라도) begin에서부터 tl개의 문자열을 비교하는 것처럼 활동하게 되고 폭파된 위치에서 begin은 비교가 이뤄지지 않아 문제가 없습니다.

코드를 보도록 하겠습니다.

#include<bits/stdc++.h>
using namespace std;
const int SZ=1000005;
int pi[SZ];
int bomb[SZ];
int vst[SZ];
string s,t;
vector<int> idx;
void bkmp(){
    int bgn=1, mch=0;
    int tl=(int)t.size();
    while(bgn+mch<tl){
        if(t[bgn+mch]==t[mch]){
            pi[bgn+mch]=mch+1;
            mch++;
        }
        else{
            if(mch==0) bgn++;
            else{
                bgn+=(mch-pi[mch-1]);
                mch=pi[mch-1];
            }
        }
    }
}
void kmp(){
    bkmp();
    int bgn=0, mch=0;
    int sl=(int)s.size();
    int tl=(int)t.size();
    while(bgn+mch<sl){
        if(!vst[bgn+mch]){
            idx.push_back(bgn+mch);
            vst[bgn+mch]=1;
        }
        if(mch<tl && s[bgn+mch]==t[mch]){
            mch++;
            bomb[bgn+mch-1]=mch;
            if(mch==tl){
                for(int i=0;i<tl;i++) idx.pop_back();
                mch=idx.size()>0?bomb[idx.back()]:0;
                bgn+=(tl-mch);
            }
        }
        else{
            if(mch==0) bgn++;
            else{
                bgn+=(mch-pi[mch-1]);
                mch=pi[mch-1];
            }
        }
    }
}
int main(void){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>s>>t;
    kmp();
    for(int xx:idx) cout<<s[xx];
    return 0;
}