Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstring>
- #include <cmath>
- #include <algorithm>
- #include <vector>
- #include <utility>
- #include <set>
- #include <map>
- #include <iostream>
- #include <queue>
- #include <climits>
- using namespace std;
- typedef long long LL;
- #define PB push_back
- #define FRO freopen("in.txt","r",stdin);
- #define CLR(arr) memset( (arr),0,sizeof(arr) );
- #define NEG(arr) memset( (arr),-1,sizeof(arr) );
- #define X first
- #define Y second
- #define MP make_pair
- #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
- typedef pair<int,int> pint;
- typedef map<int,int> mint;
- #define SIZE 1000010
- char str[SIZE];
- char pat[SIZE];
- bool pos[SIZE];
- int match[SIZE];
- vector<int> stk;
- int failure[SIZE];
- int main(){
- freopen("censor.in","r",stdin);
- freopen("censor.out","w",stdout);
- scanf("%s %s",str,pat);
- int len = strlen(str);
- int sublen = strlen(pat);
- for (int i=1, j=failure[0]= -1; i<sublen; ++i){
- while (j >= 0 && pat[j+1] != pat[i])
- j = failure[j];
- if (pat[j+1] == pat[i]) j++;
- failure[i] = j;
- }
- for (int i=0;i<len;++i){
- pos[i]=true;
- match[i] = 0;
- }
- int cnt = 0;
- for (int i=0;i<len;++i){
- if ( str[i] == pat[cnt] ){
- cnt++;
- match[i] = cnt;
- }else{
- int ind = cnt-1;
- while ( ind >= 0 && pat[ind+1] != str[i])
- ind = failure[ind];
- if (pat[ind+1] == str[i]) ind++;
- cnt = ind+1;
- match[i] = cnt;
- }
- stk.PB( i );
- if ( match[i] == sublen ){
- for (int j=0;j<sublen;++j){
- pos[ stk.back() ]=false;
- stk.pop_back();
- }
- if ( stk.size() >0 ){
- cnt = match[ stk.back() ];
- }else{
- cnt = 0;
- }
- }
- }
- for (int i=0;i<len;++i){
- if ( pos[i] ){
- printf("%c",str[i]);
- }
- }printf("\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement