Advertisement
Guest User

USACO FEB15 Censoring(SILVER)

a guest
Feb 24th, 2015
431
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define F first
  4. #define S second
  5. #define llong long long
  6. #define ullong unsigned long long
  7. #define mp make_pair
  8. #define pb push_back
  9.  
  10. using namespace std;
  11.  
  12. const int MXN = (int)1e6 + 200;
  13. const int INF = (int)1e9 + 7;
  14. const double EPS = (double)1e-9;
  15.  
  16. string s, t, st;
  17. int p[MXN];
  18. char ch[MXN];
  19. int n, m;
  20. int sz = 1;
  21.  
  22. int main(){
  23.   #define fn "censor"
  24.   #ifdef LOCAL
  25.     freopen("input.txt", "r", stdin);
  26.   #else
  27.     freopen(fn".in", "r", stdin);
  28.     freopen(fn".out", "w", stdout);
  29.   #endif
  30.   cin >> s >> t;
  31.   n = s.length();
  32.   m = t.length();
  33.   st = t + "#" + s;
  34.   for(int i = 1; i < st.length(); ++i){
  35.     int j = p[sz - 1];
  36.     while(j > 0 && st[j] != st[i])
  37.       j = p[j - 1];
  38.     if(st[i] == st[j])
  39.       ++j;
  40.     p[sz] = j;
  41.     ch[sz] = st[i];
  42.     ++sz;
  43.     if(p[sz - 1] == m)
  44.       sz -= m;
  45.   }
  46.   for(int i = m + 1; i < sz; ++i){
  47.     printf("%c", ch[i]);
  48.   }
  49.   return 0;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement