删除子串——KMP

2017年7月14日 5点热度 0条评论 来源: qianguch

题目描述:
题目来源: USACO 2015 February Contest,Silver——Problem 1
Censoring
给定一个字母串 S 和一个字母串 T ,所有字母都由小写字母 a..z 构成,S 和 T 的长度均不超过 1,000,000 ,T 的长度不会超过 S 。
从左往右枚举 S 串的每个字符,当枚举的一段连续字符串为 T ,则在 S 串中删掉这段连续字符串 T,后续字符依次向左移动填充删除的位置。然后在 S 中继续往右枚举,直到 S 串全部枚举完成为止。
请你输出最后的 S 串。
输入格式:
输入的第一行是字符串 S ,第二行是字符串 T 。
输出格式:
输出最后的 S 串。数据保证 S 串不会为空串。
样例输入:
whatthemomooofun
moo
样例输出:
whatthefun
样例说明
当枚举到 whatthemomoo 时,删除 moo ,得到 whatthemo ;
继续枚举 o ,得到 whatthemoo ,再次删除 moo ,得到 whatthe ;
继续枚举 fun ,最后得到 whatthefun 。
题目分析:
KMP。这道题的难点在于删掉一个T后,前后又可能出现一新的T串,并且怎样”删”也是一个问题,怎样才不会超时。最开始我把删掉的部分赋成0,超时;把后面的往前移,超时。最后的方法是匹配的同时依次存入一个数组,每次删掉一个T时,此数组下标就减掉一个T的长度,相当于删掉了T,然后继续存。对于合并后可能产生新的T的问题,处理见代码。
附代码:

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<queue>
#include<iomanip>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn=1e6+10;
int lens,lent,nxt[maxn],tot,pre[maxn];
char s[maxn],t[maxn],a[maxn];

int main()
{
    //freopen("lx.in","r",stdin);
    scanf("%s%s",s+1,t+1);
    lens=strlen(s+1);lent=strlen(t+1);
    for(int i=2,j=0;i<=lent;i++)
    {
        while(j!=0&&t[i]!=t[j+1]) j=nxt[j];
        if(t[i]==t[j+1]) j++; 
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=lens;i++)
    {
        while(j!=0&&s[i]!=t[j+1]) j=nxt[j];
        if(s[i]==t[j+1]) j++;
        a[++tot]=s[i];
        pre[tot]=j;//记录每一个位置的j 
        if(j==lent)
        {
            tot-=lent;//相当于a中删除了一个t字符串 
            j=pre[tot];//将删掉的t字符串的前一个位置的j付给现在,相当于跨过了t匹配,处理了合并后可能产生新的t的问题 
        }       
    }
    for(int i=1;i<=tot;i++)
        cout<<a[i];

    return 0;
}
    原文作者:qianguch
    原文地址: https://blog.csdn.net/qianguch/article/details/75104769
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。