题解

题目分析

这是一道基于哈希表和字符串匹配的题目，需要维护一个动态的字符串集合并支持模式匹配查询。

解题思路

1. 问题建模

• 维护一个动态的字符串集合，支持插入、删除和查询操作
• 查询操作：给定模式串 $s$ 和长度 $x$，计算所有长度为 $x$ 的子串在集合中的出现次数乘积
• 使用哈希表快速存储和查询字符串

2. 哈希表设计

• 使用链式哈希表处理冲突：hd[P] 存储哈希值对应的链表头
• 哈希函数：$h(s) = s \bmod P$，其中 $P = 10^7 + 331$
• 存储结构：val[i] 存储哈希值，cnt[i] 存储出现次数

3. 字符串处理

• 使用滚动哈希计算子串哈希值：$h = h \times p + s[i]$
• 基数为 $p = 233$，模数为 $mod = 998244353$
• 预计算 $p$ 的幂次：$pw[i] = p^i$

4. 关键操作

• 插入操作：add(x, y, 1) 在位置 $x$ 后插入 $y$
• 删除操作：add(x, y, -1) 删除 $x$ 到 $y$ 的连接
• 查询操作：计算模式串所有长度为 $x$ 的子串的出现次数乘积

5. 算法流程

1. 初始化哈希表和幂次数组
2. 处理插入/删除操作，更新字符串集合
3. 对查询操作，使用滚动哈希计算所有子串
4. 查询每个子串在集合中的出现次数并计算乘积

时间复杂度

• 单次操作：$O(B^2)$，其中 $B = 50$ 为最大子串长度
• 总体复杂度：$O(m \cdot B^2)$，其中 $m$ 为操作次数

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ull unsigned long long
const int N=2e5+5,M=1e7+5,mod=998244353,p=233,B=50;
const int V=1.5e7+5,P=1e7+331;
int hd[P],nxt[V],cnt[V],ct;
ull val[V];
struct Hash{
	void add(ull hs,int tp){
		int w=hs%P;
		for(int i=hd[w];i;i=nxt[i])
			if(val[i]==hs) {cnt[i]+=tp;return;}
		++ct,nxt[ct]=hd[w],hd[w]=ct,val[ct]=hs,cnt[ct]=1;
	}
	int find(ull hs){
		int w=hs%P;
		for(int i=hd[w];i;i=nxt[i])
			if(val[i]==hs) return cnt[i];
		return 0;
	}
}mp;
int n,m,a[N],nx[N],pr[N];
char s[M];
ull pw[55];
void add(int x,int y,int tp){
	int px=x,py=y;
	ull hx=0,hy;
	for(int i=1;x&&i<B;i++){
		y=py,hx=hx*p+a[x],hy=hx;
		for(int j=1;y&&j<=B-i;j++){
			hy+=pw[i+j-1]*a[y];
			mp.add(hy,tp),y=nx[y];
		}
		x=pr[x];
	}
	if(tp==1) nx[px]=py,pr[py]=px;
	else nx[px]=pr[py]=0;
}
int main(){
	pw[0]=1;
	for(int i=1;i<=B;i++) pw[i]=pw[i-1]*p;
	int op,x,y;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),mp.add(a[i],1);
	while(m--){
		scanf("%d",&op);
		if(op==1)
			scanf("%d%d",&x,&y),add(x,y,1);
		else if(op==2){
			scanf("%d",&x);
			int y=nx[x];
			add(x,y,-1);
		}
		else{
			scanf("%s%d",s+1,&x);
			int len=strlen(s+1);
			ll ans=1;ull hs=0;
			for(int i=len;i>=len-x+1;i--) hs=hs*p+s[i]-'0';
			for(int i=len-x+1;i>=1;i--){
				ans=ans*mp.find(hs)%mod;
				hs-=pw[x-1]*(s[i+x-1]-'0');
				hs=hs*p+s[i-1]-'0';
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}