首页 > 其他 > 详细

SCU oj 4438:Censor

时间:2017-08-21 11:52:10      阅读:265      评论:0      收藏:0      [点我收藏+]

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

.

(1length of w,p5?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("\n");
}
int main(){
    while(scanf("%s%s",w,t)!=EOF){
        get_next(w);
        Kmp(t,w);
    }
    return 0;
}

 

 

SCU oj 4438:Censor

原文:http://www.cnblogs.com/liyinggang/p/7403537.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!