Advertisement
Guest User

Untitled

a guest
Feb 26th, 2015
478
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.08 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <utility>
  7. #include <set>
  8. #include <map>
  9. #include <iostream>
  10. #include <queue>
  11. #include <climits>
  12.  
  13. using namespace std;
  14.  
  15. typedef long long LL;
  16.  
  17. #define PB push_back
  18. #define FRO freopen("in.txt","r",stdin);
  19.  
  20. #define CLR(arr) memset( (arr),0,sizeof(arr) );
  21. #define NEG(arr) memset( (arr),-1,sizeof(arr) );
  22.  
  23. #define X first
  24. #define Y second
  25.  
  26. #define MP make_pair
  27.  
  28. #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
  29.  
  30.  
  31. typedef pair<int,int> pint;
  32. typedef map<int,int> mint;
  33.  
  34. #define SIZE 1000010
  35.  
  36. char str[SIZE];
  37. char pat[SIZE];
  38.  
  39.  
  40. bool pos[SIZE];
  41.  
  42. int match[SIZE];
  43.  
  44. vector<int> stk;
  45. int failure[SIZE];
  46.  
  47. int main(){
  48.  
  49.     freopen("censor.in","r",stdin);
  50.     freopen("censor.out","w",stdout);
  51.  
  52.     scanf("%s %s",str,pat);
  53.  
  54.     int len = strlen(str);
  55.     int sublen = strlen(pat);
  56.  
  57.     for (int i=1, j=failure[0]= -1; i<sublen; ++i){
  58.         while (j >= 0 && pat[j+1] != pat[i])
  59.             j = failure[j];
  60.         if (pat[j+1] == pat[i]) j++;
  61.         failure[i] = j;
  62.     }
  63.  
  64.     for (int i=0;i<len;++i){
  65.         pos[i]=true;
  66.         match[i] = 0;
  67.     }
  68.  
  69.     int cnt = 0;
  70.     for (int i=0;i<len;++i){
  71.         if ( str[i] == pat[cnt] ){
  72.             cnt++;
  73.             match[i] = cnt;
  74.         }else{
  75.             int ind = cnt-1;
  76.             while ( ind >= 0 && pat[ind+1] != str[i])
  77.                 ind = failure[ind];
  78.             if (pat[ind+1] == str[i]) ind++;
  79.  
  80.             cnt = ind+1;
  81.             match[i] = cnt;
  82.  
  83.         }
  84.  
  85.         stk.PB( i );
  86.  
  87.  
  88.         if ( match[i] == sublen ){
  89.             for (int j=0;j<sublen;++j){
  90.                 pos[ stk.back() ]=false;
  91.                 stk.pop_back();
  92.             }
  93.             if ( stk.size() >0 ){
  94.                 cnt = match[ stk.back() ];
  95.             }else{
  96.                 cnt = 0;
  97.             }
  98.         }
  99.     }
  100.  
  101.  
  102.     for (int i=0;i<len;++i){
  103.         if ( pos[i] ){
  104.             printf("%c",str[i]);
  105.         }
  106.     }printf("\n");
  107.  
  108.     return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement