luogu P4465 [国家集训队] JZPSTR

题面传送门

我真的，我哭死，如果考了我当场感谢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());
		}
	}
}