9935번: EKSPLOZIJA

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

스택에 Mirko의 문자를 하나씩 넣어보면서 마지막 부분이 폭발 문자열이면 해당 문자들을 제거한다.

아래 소스의 시간복잡도는 $O(l_tl_p)$

#include<cstdio>
#include<cstring>
int n, l;
char t[1000001], p[37], s[1000001];
int main() {
    scanf("%s%s", t, p);
    l = strlen(p);
    for (int i = 0; t[i]; i++) {
        s[n++] = t[i];
        if (n >= l &&!strncmp(s + n - l, p, l)) n -= l;
    }
    s[n] = 0;
    puts(n ? s : "FRULA");
    return 0;
}