LG4824 「USACO2015FEB」(Silver)Censoring KMP+栈

问题描述

LG4824

题解

大概需要回顾（看了题解）

KMP

先对要删除的 模式串 进行自我匹配，求出 \(\mathrm{fail}\)

然后再扫 文本串 的过程中记录一下每个字符匹配的最大长度，用栈进行删除。

这类删除一段连续区间的问题常用栈来优化维护

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

char a[1000007],b[1000007];
int n,m;
int fail[1000007];

void KMP(){
    for(int i=2,j=0;i<=m;i++){
        while(j&&b[i]!=b[j+1]) j=fail[j];
        if(b[i]==b[j+1]) ++j;
        fail[i]=j;
    }
}

int sta[1000007],top;
int opt[1000007];

void solve(){
    for(int i=1,j=0;i<=n;i++){
        while(j&&a[i]!=b[j+1]) j=fail[j];
        if(a[i]==b[j+1]) ++j;
        opt[i]=j;sta[++top]=i;
        if(j==m){
            top-=j;
            j=opt[sta[top]];
        }
    }
    for(int i=1;i<=top;i++) putchar(a[sta[i]]);
    puts("");
}

int main(){
    ios::sync_with_stdio(0);
    cin>>(a+1);n=strlen(a+1);
    cin>>(b+1);m=strlen(b+1);
    KMP();
    solve();
    return 0;
}