검열2 (JUNGOL 2842)

https://jungol.co.kr/problem/2842

---

아이디어

하나씩 넣으면서 now를 지금까지 넣은 문자들의 맨 뒤에 최대 now개를 고르면 원하는 target 문자열이 된다. 라고 정의합시다. 만약 now가 target문자열의 길이와 같아지면, 제거할 수 있는 것입니다. 이때 now가 증가하다가 원하는 문자가 나오지 않을 때가 있는데 그러면 target의 pi 배열을 미리 만들어서 now값으로 가능한 값을 빠르게 감소시켜주면 됩니다.

---

소스코드

#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

vector <ll> GetPi(string s)
{
    ll N=s.length(),idx=0;
    vector <ll> Pi(N);

    for (ll i=1;i<N;i++)
    {
        while (idx && s[idx]!=s[i]) idx=Pi[idx-1];
        if (s[idx]==s[i]) Pi[i]=++idx;
    }

    return Pi;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    string s,target;
    ll N;

    cin>>s>>target;
    N=s.length();

    vector <ll> Pi=GetPi(target);

    stack <pair <char,ll> > stk;
    ll now=0;

    for (ll i=0;i<N;i++)
    {
        while (now && target[now]!=s[i]) now=Pi[now-1];
        if (target[now]==s[i]) now++;
        stk.push({s[i],now});

        if (now==target.length())
        {
            ll T=target.length();
            while (T--) stk.pop();
        }

        if (stk.size()) now=stk.top().second;
        else now=0;
    }

    stack <char> res;
    while (stk.size())
    {
        res.push(stk.top().first);
        stk.pop();
    }

    while (res.size())
    {
        cout<<res.top();
        res.pop();
    }
}