首页 > 其他 > 详细

P4824 [USACO15FEB]Censoring (Silver) 审查(银)

时间:2018-09-21 10:38:17      阅读:178      评论:0      收藏:0      [点我收藏+]

传送门

一个串的匹配肯定考虑KMP

那就暴力KMP

记录一下到每个字符时匹配的位置

找到一个符合的串就标记然后暴力回跳

感觉好像太暴力了...

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e6+7;
char ch[N],a[N];
int f[N],match[N];
bool pd[N];
int main()
{
    scanf("%s",ch); scanf("%s",a); 
    int len=strlen(ch),la=strlen(a),k=0;
    for(int i=1;i<la;i++)
    {
        while(k&&a[i]!=a[k]) k=f[k];
        f[i+1]= a[i]==a[k] ? ++k : 0;
    }
    //以下为暴力匹配
    int i=0; k=0;
    while(i<len)
    {
        while(k&&a[k]!=ch[i]) k=f[k];
        if(a[k]==ch[i]) k++;
        
        if(k==la)//找到匹配就暴力回跳
        {
            int j=1;
            while(j<=la)
            {
                if(pd[i])
                {
                    i--;
                    continue;
                }
                pd[i]=1,i--;
                j++;
            }
            while(pd[i]) i--;//最后还要跳一波
            k=match[i];
        }
        match[i]=k;
        i++;
        while(pd[i]) i++;
    }
    for(int i=0;i<len;i++)
    {
        if(pd[i]) continue;
        cout<<ch[i];
    }
    return 0;
}

膜一下CRK大佬,用的是AC自动机%%%

P4824 [USACO15FEB]Censoring (Silver) 审查(银)

原文:https://www.cnblogs.com/LLTYYC/p/9684851.html

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