SCU 4438:Censor

Censor

frog is now a editor to censor so-called sensitive words (敏感词).

She has a long text p

. Her job is relatively simple -- just to find the first occurence of sensitive word w

and remove it.

frog repeats over and over again. Help her do the tedious work.

Input

The input consists of multiple tests. For each test:

The first line contains 1

string w. The second line contains 1 string p

.

(1≤length of w,p≤5⋅106

, w,p

consists of only lowercase letter)

Output

For each test, write 1

string which denotes the censored text.

Sample Input

    abc
    aaabcbc
    b
    bbb
    abc
    ab

Sample Output

    a
    
    ab

题意: 给你一个主串,递归删除模式串。
比如: T: abc  S: aaabcbc    
aaabcbc->aabc->a

非常巧妙的KMP,我们用一个栈记录当前的字符以及其在模式串匹配的位置,当位置等于模式串长度之后,将模式串长度的串出栈,从栈顶元素开始继续匹配主串.时间复杂度 O(n).

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stack>
#include <algorithm>
using namespace std;
const int N = 5000005;
struct Node{
    char c;
    int k;
};
char w[N],t[N],ans[N];
int Next[N];
void get_next(char *p){
    int len = strlen(p);

    int i=0,k=-1;
    Next[0] = -1;
    while(i<len){
        if(k==-1||p[i]==p[k]){
            i++,k++;
            Next[i] = k;
        }
        else k = Next[k];
    }
}

void Kmp(char *s,char *p){
    int len1 = strlen(s),len2 = strlen(p);
    int i=0,j=0,len;
    stack <Node> stk;
    while(!stk.empty()) stk.pop();
    while(i<len1){
        if(j==-1||s[i]==p[j]){
            i++,j++;
            stk.push(Node{s[i-1],j});
        }else {
            j=Next[j];
        }
        if(j==len2){
            len = len2;
            while(!stk.empty()&&len--) stk.pop();
            if(stk.empty()) j = 0;
            else j = stk.top().k;
        }
    }
    int k = 0;
    while(!stk.empty()){
        ans[k++] = stk.top().c;
        stk.pop();
    }
    for(int i=k-1;i>=0;i--) printf("%c",ans[i]);
    printf("
");
}
int main(){
    while(scanf("%s%s",w,t)!=EOF){
        get_next(w);
        Kmp(t,w);
    }
    return 0;
}