搜索

luogu P4465 [国家集训队] JZPSTR


发布时间: 2022-11-24 21:03:03    浏览次数:33 次

题面传送门

我真的,我哭死,如果考了我当场感谢zyq。

听说std是SAM+块链,我瑟瑟发抖,然后祭出了bitset大法。

据说这个是叫一种Shift-And的基于位运算的字符串匹配算法,也就是说,我们维护每个字符在哪些位置上出现过,记\(i\)字符出现在\(f_i\)集合的位置,现有匹配串\(s\),维护当前仍然合法的起始点集合\(p\),则有\(p=p\and (f_{s_i}>>i)\)

这个东西在平凡情况下会被KMP干爆,但是在这种带修的地方就能显露出优势。修改其实就是将一部分左移,然后加入,删除就是将一部分右移,查询直接按照上面的查询,复杂度就是\(O(\frac{QL}{w})\)

code:

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=1e6+5,M=N*4+5,K=1e5+5,mod=1e9+7,Mod=mod-1,INF=1e9+7;const db eps=1e-5;mt19937 rnd(time(0));
int T,k,op,x,y;char c[N];
bitset<N> f[10],T1,T2,T3,Ans,Cl;
int main(){
	freopen("1.in","r",stdin);
	int i,j;scanf("%d",&T);for(i=0;i<1e6;i++) Cl[i]=1;while(T--){
		scanf("%d%d",&op,&x);if(!op){
			scanf("%s",c);k=strlen(c);for(i=0;i<10;i++) T1=(f[i]>>x)<<x,f[i]^=T1,f[i]|=T1<<k;
			for(i=0;i<k;i++) f[c[i]-'0'][x+i]=1;
		}else if(scanf("%d",&y),op==1){
			for(i=0;i<10;i++) T1=(f[i]>>x)<<x,f[i]^=T1,T1=(T1>>y)<<x,f[i]|=T1;
		}else{
			scanf("%s",c);k=strlen(c);if(k>y-x){puts("0");continue;}Ans=Cl;for(i=0;i<k;i++) Ans=Ans&(f[c[i]-'0']>>i);
			Ans>>=x;printf("%d\n",(Ans^((Ans>>y-x-k+1)<<y-x-k+1)).count());
		}
	}
} 
免责声明 luogu P4465 [国家集训队] JZPSTR,资源类别:文本, 浏览次数:33 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 09:03:03。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/275307894a/p/16923288.html