10747번: Censoring

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

$O(l)$

kmp 알고리즘을 돌리면서 패턴을 찾으면 j(아래 소스)를 패턴이 시작했던 지점에서의 j로 바꿔준다.
스택에 s의 문자를 하나씩 넣다가 패턴을 찾으면 최근 t개의 길이만큼 pop시킨다.

반복문이 끝난 후 스택에 있는 문자들을 모두 빼서 반대 순서로 출력하면 답.

#include<cstdio>
const int MXL = 1e6;
char s[MXL + 1], t[MXL + 1], r[MXL + 1];
int pi[MXL + 1] = { -1 }, a[MXL + 1], n;
int main() {
    scanf("%s%s", s, t);
    for (int i = 0, j = -1; t[i];) {
        if (j < 0 || t[i] == t[j]) pi[++i] = ++j;
        else j = pi[j];
    }
    for (int i = 0, j = 0; s[i];) {
        if (j < 0 || s[i] == t[j]) {
            r[n++] = s[i++];
            a[n] = ++j;
            if (!t[j]) j = a[n -= j];
        }
        else j = pi[j];
    }
    r[n] = 0;
    puts(r);
    return 0;
}