USACO FEB15 Censoring(SILVER)

#include <bits/stdc++.h>

#define F first
#define S second
#define llong long long
#define ullong unsigned long long
#define mp make_pair
#define pb push_back

using namespace std;

const int MXN = (int)1e6 + 200;
const int INF = (int)1e9 + 7;
const double EPS = (double)1e-9;

string s, t, st;
int p[MXN];
char ch[MXN];
int n, m;
int sz = 1;

int main(){
  #define fn "censor"
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #else
    freopen(fn".in", "r", stdin);
    freopen(fn".out", "w", stdout);
  #endif
  cin >> s >> t;
  n = s.length();
  m = t.length();
  st = t + "#" + s;
  for(int i = 1; i < st.length(); ++i){
    int j = p[sz - 1];
    while(j > 0 && st[j] != st[i])
      j = p[j - 1];
    if(st[i] == st[j])
      ++j;
    p[sz] = j;
    ch[sz] = st[i];
    ++sz;
    if(p[sz - 1] == m)
      sz -= m;
  }
  for(int i = m + 1; i < sz; ++i){
    printf("%c", ch[i]);
  }
  return 0;
}