首页 > 其他分享 >P4824 [USACO15FEB] Censoring S

P4824 [USACO15FEB] Censoring S

时间:2023-03-08 15:34:06浏览次数:44  
标签:f2 int pow hh vb Censoring USACO15FEB P4824 strlen

希望在Str 中删掉 1个屏蔽词(一个屏蔽词可能出现多次)

求最后的串

 

栈+hash

 

#include <iostream>
#include <cstring> 
using namespace std; 
 const int N =1e6+3;
 #define int long long
int bas=29,pow[N],h[N];
char a[N],b[N];
int n,m, st[N],hh;

 int f2(int l,int r){
     return h[r]-h[l-1]*pow[r-l+1];
 }
 signed main(){
 	int i,j;
 	pow[0]=1;
 	for(i=1;i<=1e6;i++) pow[i]=pow[i-1]*bas;
 	cin>>a+1>>b+1;
 	n=strlen(a+1),m=strlen(b+1);
 	
 	int vb= 0;
 	for(i=1;i<=m;i++)
 		vb =vb*bas+b[i];
 		
 	for(i=1;i<=n;i++){
 		st[++hh]=a[i]; h[hh]=h[hh-1]*bas+a[i];
 		if(hh-m+1>=1&&f2(hh-m+1,hh)==vb) hh-=m;
 	}
 	for(i=1;i<=hh;i++) cout<<char(st[i]);
 }

 

标签:f2,int,pow,hh,vb,Censoring,USACO15FEB,P4824,strlen
From: https://www.cnblogs.com/towboa/p/17192135.html

相关文章