题解 P4824 【[USACO15FEB]Censoring (Silver) 审查(银)】

· · 题解

\mathtt{Update\ 2019.11.08}

题面

在字符串 A 中，如果字符串 B 是 A 的子串，那么就删除在 A 中第一个出现的 B，然后拼接在一起，一直重复上述步骤直到 B 不再是 A 的子串

|A|\le 10^6

解题思路

KMP+栈

分析

1、字符串匹配的问题，想到 KMP

2、在匹配过程中，如果匹配成功了，就将子串 B 删除，可以证明，对之前不会产生影响

3、删了再加入，类似栈的操作，因此用栈维护上述操作过程中的字串即可

过程

1、KMP 板子跑一遍

2、在 KMP 过程中，把遍历到的 i（不是字符，而是下标）入栈，当匹配上 B 时，就把匹配的部分出栈，然后 j 从栈顶的 i 所能匹配到的最大的位置开始（就是 f[i] 记录的值），继续做 KMP

时间复杂度：B 自身匹配一次 +A 与 B 匹配一次+A 中最多每个字符进出栈一次，为 O(|A|)

Code

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int la,lb,res;
char a[N],b[N];
int p[N],f[N];//分别表示B串自身匹配的结果、A串与B串匹配的结果
int St[N],top;
int main()
{
    int i,j;
    scanf("%s",a+1);
    scanf("%s",b+1);
    la=strlen(a+1);
    lb=strlen(b+1);
    for(i=2,j=0;i<=lb;i++) {//自身匹配
        while(j&&b[i]!=b[j+1])
            j=p[j];
        if(b[i]==b[j+1])
            j++;
        p[i]=j;
    }
    for(i=1,j=0;i<=la;i++) {//A与B匹配
        while(j&&a[i]!=b[j+1])
            j=p[j];
        if(a[i]==b[j+1])
            j++;
        f[i]=j;//记录结果
        St[++top]=i;//入栈
        if(j==lb)//如果匹配成功，弹出，并更新j值
            top-=lb,j=f[St[top]];
    }
    for(i=1;i<=top;i++)//大功率输出
        printf("%c",a[St[i]]);
    return 0;
}

再扔道题 Luogu P3121 [USACO15FEB]审查（黄金）Censoring (Gold)