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;

}

巴特西

LG4824 「USACO2015FEB」(Silver)Censoring KMP+栈

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章