SCU 4438:Censor

时间:2021-09-06 20:48:19

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