BZOJ 3942 Usaco2015 Feb Censoring KMP算法
浏览数：17 /
时间：2015年06月08日
题目大意：给定两个串A和B，要求将A中删掉所有的B后输出
为何BC群刚有人问完我这题的【C++语法基础题】版之后就出了个KMP版的= =
维护一个栈，将A中的字符依次加进去，一旦A的栈顶出现了B就弹栈
用KMP算法来加速这个过程即可
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 1001001
using namespace std;
int len;
char s1[M],s2[M];
int next[M];
char stack[M];
int a[M],top;
void KMP(char s[])
{
int i,fix=0;
for(i=2;s[i];i++)
{
while( fix && s[i]!=s[fix+1] )
fix=next[fix];
if(s[i]==s[fix+1])
++fix;
next[i]=fix;
}
}
int main()
{
int i;
scanf("%s%s",s1+1,s2+1);
len=strlen(s2+1);KMP(s2);
for(i=1;s1[i];i++)
{
stack[++top]=s1[i];
int fix=a[top-1];
while(fix&&s2[fix+1]!=stack[top])
fix=next[fix];
if(s2[fix+1]==stack[top])
++fix;
a[top]=fix;
if(a[top]==len)
top-=len;
}
stack[top+1]=0;
puts(stack+1);
return 0;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
