bzoj 3942: [Usaco2015 Feb]Censoring【kmp+栈】

好久没写kmp都不会写了……

开两个栈，s存当前串，c存匹配位置

用t串在栈s上匹配，栈每次入栈一个原串字符，用t串匹配一下，如果栈s末尾匹配了t则弹栈

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=1000005;

int n,m,c[N],top,ne[N];

char a[N],b[N],s[N];

void gtnxt()

{

    ne[0]=-1;

    for(int i=1,j=-1;i<n;i++)

    {

        while(j!=-1&&b[i]!=b[j+1])

			j=ne[j];

        if(b[i]==b[j+1])

			j++;

        ne[i]=j;

    }

}

int main()

{

	scanf("%s%s",a,b);

	n=strlen(a),m=strlen(b);

	gtnxt();

	for(int i=0;i<n;i++)

	{

		int j=c[top];

		s[++top]=a[i];

		while(j!=-1&&b[j+1]!=s[top])

			j=ne[j];

		if(b[j+1]==s[top])

			j++;

		c[top]=j;

		if(c[top]==m-1)

			top-=m;

	}

	s[top+1]='\0';

    puts(s+1);

	return 0;

}

巴特西

bzoj 3942: [Usaco2015 Feb]Censoring【kmp+栈】

最新文章

热门文章