fork(1) download 
  1. #include <iostream>
  2. #include <string>
  3. #include <stdio.h>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <map>
  7. #include <vector>
  8. #include <iomanip>
  9. #include <stack>
  10. #include <queue>
  11.  
  12.  
  13. using namespace std;
  14.  
  15. #define ll long long
  16. #define DEBUG(X) { cerr << #X << " : " << X <<endl; }
  17. #define FOR(i,a,b) for(int i = a , _##i = (b) ; i <= _##i  ; i++)
  18. #define FOD(i,a,b) for(int i = a , _##i = (b) ; i >= _##i ; i--)
  19. #define sqr(x) ((x)*(x))
  20. #define SZ(s) s.size()
  21. #define ALL(a) a.begin() , a.end()
  22. #define MAXN 1000005
  23. #define MOD 1000000007
  24. #define TIE cin.tie(0)
  25. #define SYNC ios::sync_with_stdio(0)
  26. #define min3(a1,a2,a3) min((a1),min((a2),(a3)))
  27. #define ii pair<int,int>
  28. #define llp pair<ll, ll>
  29. #define lmp(a,b) make_pair((a), (b))
  30.  
  31. const int maxn = 1000010;
  32. int b[maxn];
  33. string s, p;
  34. int n, m;
  35.  
  36. void preKMP() {
  37.     int i =0, j = -1;
  38.     b[0] = -1;
  39.  
  40.     while(i < m) {
  41.         while(j >= 0 && p[i] != p[j]) j = b[j];
  42.         i++;
  43.         j++;
  44.  
  45.         b[i] = j;
  46.     }
  47. }
  48.  
  49. int compareKMP() {
  50.     int i = 0, j = 0 ;
  51.     while(i < n) {
  52.         while(j >= 0 && s[i] != p[j]) j = b[j];
  53.         i++; j++;
  54.         if(j == m) {
  55.        //     cout << "Find at " << i - m << " length = " << m << endl;
  56.             s.erase(i - m, m);
  57.             return 1;
  58.         }
  59.     }
  60.  
  61.     return 0;
  62. }
  63.  
  64. int main() {
  65.     SYNC;
  66.     TIE;
  67.  
  68.     cin >> s >> p;
  69.     n = s.length();
  70.     m = p.length();
  71.  
  72.     preKMP();
  73.     while(compareKMP()) {
  74.  
  75.     }
  76.  
  77.     cout << s;
  78. }
  79.  
Success #stdin #stdout 0s 19136KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/WZZ87n
P153SUMA , KMP, String
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!