首页 > 代码库 > bzoj3942[Usaco2015 Feb]Censoring*
bzoj3942[Usaco2015 Feb]Censoring*
bzoj3942[Usaco2015 Feb]Censoring
题意:
有一个S串和一个T串,不断地在S串里匹配T串,然后将其删除。S串、T串长度≤1000000。
题解:
用1、2两个栈,每次将S串的当前字符压入1栈,当前匹配到T串的位置压入2栈,如果匹配出一个T串,则让1、2栈中匹配T串的子串出栈,然后令当前匹配到T串的位置变为2栈顶的数,匹配过程可以用KMP加速。
代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 1000010 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 using namespace std; 7 8 char s[maxn],t[maxn],st1[maxn]; int lens,lent,st2[maxn],top,fail[maxn]; 9 void getfail(){10 int j=0;11 inc(i,2,lent){12 while(j&&t[i]!=t[j+1])j=fail[j];13 if(t[i]==t[j+1])j++; fail[i]=j;14 }15 }16 int main(){17 char ch=getchar(); while(ch<‘a‘||ch>‘z‘)ch=getchar();18 lens=0; while(ch>=‘a‘&&ch<=‘z‘)s[++lens]=ch,ch=getchar();19 ch=getchar(); while(ch<‘a‘||ch>‘z‘)ch=getchar();20 lent=0; while(ch>=‘a‘&&ch<=‘z‘)t[++lent]=ch,ch=getchar();21 getfail(); int j=0,top=0;22 inc(i,1,lens){23 while(j&&s[i]!=t[j+1])j=fail[j]; if(s[i]==t[j+1])j++;24 st1[++top]=s[i],st2[top]=j;25 if(j==lent){while(j)top--,j--; j=st2[top];}26 }27 inc(i,1,top)printf("%c",st1[i]); return 0;28 }
20160825
bzoj3942[Usaco2015 Feb]Censoring*
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。