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
abSample 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 ;
}