自动搬运

查看原文

来自洛谷，原作者为

	enucai Remake.

搬运于2025-08-24 22:39:11，当前版本为作者最后更新于2022-07-27 16:04:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Preface

做法0：我不会数据结构！

期望得分：100。

真的想骂骂这个数据啊。

Analysis

乱搞选手，复杂度不正确，可惜出题人没有卡。

算法：字符串 hash。

首先想用一个容器记录一下每次询问后的字符串集。每个字符串记录其长度与 hash 值。

对于操作 1，直接计算字符串 $s$ 的 hash 值，并将其加入容器。

对于操作 2，则直接遍历容器中的元素，并枚举 $s$ 的起始位置，用字符串 hash 的前缀和快速算出这一个子串的 hash 值。若相等，则答案 $+1$。

注意容器的选择，应用 multiset 而不是 set。但是直接用 set 会 MLE，因此选择在使用 set 的同时记录一下这种串的个数即可。

最坏时间复杂度 $O(q^2)$，莫名其妙就过了。

Code

#include<bits/stdc++.h>
using namespace std;
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define Rof(i,j,k) for(int i=(j);i>=(k);i--)
#define mkp make_pair
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ull unsigned long long
#define int long long
const ull B=13331;
set<pair<pair<ull,int>,int>> S[500010];
ull sum[1000010],mi[1000010];
int q;
char s[1000010];
signed main(){IOS;
	mi[0]=1;
	For(i,1,1000000) mi[i]=mi[i-1]*B;
	cin>>q; S[0].clear();
	For(_,1,q){
		int op,__; cin>>op>>__>>(s+1);
		int m=strlen(s+1);
		S[_]=S[__];
		if(op==1){
			ull now=0ull;
			For(i,1,m) now=now*B+(ull)(s[i]-'a');
			auto tmp=S[_].lower_bound(mkp(mkp(now,m),0));
			if(tmp->fi==mkp(now,m)){
				int cnt=tmp->se;
				S[_].erase(tmp),S[_].emplace(mkp(now,m),cnt+1);
			}else{
				S[_].emplace(mkp(now,m),1);
			}
		}else{
			sum[0]=0ull;
			For(i,1,m) sum[i]=sum[i-1]*B+(ull)(s[i]-'a');
			int res=0;
			for(auto[hl,cnt]:S[_]){
				For(i,1,m-hl.se+1) if(sum[i+hl.se-1]-sum[i-1]*mi[hl.se]==hl.fi) res+=cnt;
			}
			cout<<res<<"\n";
		}
	}
}