fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. #define mod 1000000009LL
  5. #define base 257
  6. const int N = 1000000;
  7. struct hashed_string{
  8.     public:
  9.     ll n;
  10.     vector <ll> prefix;
  11.     vector <ll> pow;
  12.     hashed_string(){
  13.         n = 0;
  14.         pow.assign(N+1, 0);
  15.         prefix.assign(N+1,0);
  16.         pow[0] = 1;
  17.         for (int i = 1; i <= N; i++){
  18.             pow[i] = (pow[i-1] * base) % mod;
  19.         }
  20.     }
  21.     void addhash(char a){
  22.         prefix[n] = ((n >= 1 ? prefix[n-1] * base % mod : 0) + (a - '0')) % mod;
  23.         n++;
  24.     }
  25.     void delhash(ll x){
  26.         for (int i = 0; i < x; i++){
  27.             n--;
  28.             prefix[n] = 0;
  29.         }
  30.     }
  31.     ll get_hash(ll l, ll r){
  32.         ll x = prefix[r];
  33.         if (l >= 1){
  34.             l--;
  35.             x = ((x - prefix[l] * pow[r - l] % mod) % mod + mod) % mod;
  36.         }
  37.         return x;
  38.     }
  39. };
  40. void solve(){
  41.     string pile;
  42.     string target;
  43.     hashed_string w;
  44.     cin >> pile >> target;
  45.     for (auto &p : target){
  46.         w.addhash(p);
  47.     }
  48.     hashed_string cur;
  49.     string v;
  50.     int p = 0;
  51.     for (int i = 0; i < pile.size(); i++){
  52.         cur.addhash(pile[i]);
  53.         v.push_back(pile[i]);
  54.         while (cur.n >= target.size() && cur.get_hash(cur.n - target.size(), cur.n - 1) == w.get_hash(0, w.n - 1)){
  55.             cur.delhash(target.size());
  56.             for (int j = 0; j < target.size(); j++){
  57.                 v.pop_back();
  58.             }
  59.         }
  60.     }
  61.     cout << v;
  62. }
  63. int main(){
  64.     freopen("censor.in","r",stdin);
  65.     freopen("censor.out","w",stdout);
  66.     solve();
  67.     return 0;
  68. }
Success #stdin #stdout 0.02s 34660KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/T7V8u2
language:
C++14 (clang 8.0)
created:
4 hours ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!