欢迎来我 Luogu 博客看啊。

Hydro 上开了火车头才过...

引言

这题是Claris教的，说：我两三年前在bzoj做这题时，只有两个提交，一个是出题人自己交的，还有一个是交出题人代码的。

然后这道原来正解是块状链表+后缀自动机的题目被Claris用bitset暴力匹配吊打了标算。sro Claris！

shift-and算法

由于懒，用的是C++自带的std::bitset。这是道黑题，其具体用法就挂个链接了。

记 $m=10$。考虑到字符集只有 $10$ 位，开 $m$ 个bitset储存各个位置，即 std::bitset<1000005>B[10];

对于 $0,1$ 修改操作利用位运算暴力改，复杂度大约是 $O(\frac{nm} w)$ 的。但 $0$ 操作还涉及增加串长度，不过这可以用插入总长度复杂度抛掉。

对于 $2$ 查询操作则用shift-and算法，对长度为 $l$ 的模式串C，设答案可取位对应的bitset初值为 00011111000 式的（仅对答案可能存在的 $[x,y)$ 赋一）的p，则反复 p=(p<<1)&B[C[j]-'0'] 即可。把p左移就相当于把文本串右移。注意第一次不必左移。复杂度大约是 $O(\frac{nl}w)$。

Code

人傻常数大，开了O2才过。

代码轻微压行，不到1KB，比较短。

#include <bitset>
#include <stdio.h>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
std::bitset<1000005>B[10],p;chr C[1919810];
int main()
{
	uint q=0,op,num1,num2,f;scanf("%u",&q);
	while(q--)
	{
		scanf("%u%u",&op,&num1);
		if(op)
			if(op==1)
			{
				scanf("%u",&num2);
				for(uint i=0;i<10;i++)p=(B[i]>>num2)<<num2,B[i]^=((B[i]>>num1)<<num1)^(p>>(num2-num1));
			}
			else
			{
			    scanf("%u%s",&num2,C),p=std::bitset<1000005>();
                for(f=0;C[f];f++);
                p=((~p)<<num1)^((~p)<<(num2-f+1));
                for(uint j=0;j<f;j++)p=(j?(p<<1):p)&B[C[j]-'0'];
                printf("%d\n",(int)p.count());
			}
		else
		{
			scanf("%s",C);
			for(f=0;C[f];f++);
			for(uint i=0;i<10;i++)p=(B[i]>>num1)<<num1,B[i]^=p^(p<<f);
			for(uint i=0;i<f;i++)B[C[i]-'0'][num1+i]=true;
		}
	}
	return 0;
}

后记

第一次写黑题题解，有所勘误恳请指出。

bitset在字符串匹配上有所应用，一般不超过 $100000$ 且字符集较小的可以代替kmp。

Claris：这题究竟没有躲过暴力。

还是sro Claris！

END