题解

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define HM 1000000007
#define HA 100000007
#define HB 101

int hext(int h, int ch) {
  return (1ll * h * HA + ch + HB) % HM;
}

int main() {
  string S, T;
  cin >> S >> T;
  int thsh = 0;
  for (int i = 0; i < T.size(); i++) {
    thsh = hext(thsh, T[i] - 'a');
  }
  string R;
  vector<int> rhsh(1, 0);
  vector<int> HAPW(1, 1);
  for (int i = 0; i < S.size(); i++) {
    R += S[i];
    rhsh.push_back(hext(rhsh.back(), S[i] - 'a'));
    HAPW.push_back((1ll * HAPW.back() * HA) % HM);

    if (R.size() >= T.size()) {
      int hsub = (1ll * rhsh[R.size() - T.size()] * HAPW[T.size()]) % HM;
      int hsh = (HM + rhsh.back() - hsub) % HM;
      if (hsh == thsh && R.substr(R.size() - T.size()) == T) {
        R.resize(R.size() - T.size());
        rhsh.resize(rhsh.size() - T.size());
        HAPW.resize(HAPW.size() - T.size());
      }
    }
  }

  cout << R << endl;
  return 0;
}