Codeforces 1466G - Song of the Sirens（哈希）

Codeforces 题面传送门 & 洛谷题面传送门

事实证明，有的难度评分不算很高、涉及的知识点不算很难的题目也能出得非常神仙

首先考虑如何暴力求答案。注意到一个文本串 \(T\) 在 \(s_k\) 中出现的位置，有两种可能，要么跨过中间的 \(t_k\)，要么没跨过，前者等价于文本串在 \(s_{k-1}[|s_{k-1}|-|T|+2,|s_{k-1}|]+t_k+s_{k-1}[1,|T|-1]\) 中出现的次数。由于其长度为 \(\mathcal O(|T|)\)，因此可以在 KMP 或哈希在 \(\mathcal O(|T|)\) 时间内求出。要么没有跨过中间的 \(t_k\)，而这样的出现位置要么在 \(s_0\) 中出现过，要么在某个 \(s_{k'}(k' 中作为跨过中间的 \(t_{k'}\) 的字符串出现。因此

其中 \(\text{occ}(s,t)\) 表示 \(t\) 在 \(s\) 中的出现次数。

考虑优化。我们找到最小的 \(k'\)，满足 \(|t_{k'}|>|T|\)，如果不存在这样的 \(k'\) 或 \(k'>k\) 则直接输出 \(\text{occ}(t_k,T)\) 即可。否则我们先令答案加上 \(\text{occ}(t_{k'},T)·2^{k-k'}\)，而对于 \(i>k',j>k'\)，由于 \(|T|<|s_i|,|T|<|s_j|\)，如果 \(t_i=t_j\)，那么显然有 \(s_{i}[|s_{i}|-|T|+2,|s_{i}|]+t_i+s_{i}[1,|T|-1]=s_{j}[|s_{j}|-|T|+2,|s_{j}|]+t_j+s_{j}[1,|T|-1]\)，我们考虑枚举所有 \(t_j=c\)，计算 \(\text{occ}(s_{i}[|s_{i-1}|-|T|+2,|s_{i}|]+c+s_{i}[1,|T|-1],T)\)，然后前缀和求出 \(\sum\limits_{i=k'+1}^k2^{-i}[t_i=c]\)，这样即可在 \(|T|·|\Sigma|\) 的时间内算出答案。

时间复杂度 \(\Theta((\sum|T|+n)·|\Sigma|)\)

const int MAXN=1e5;
const int MAXM=100;
const int MAXL=1e6;
const int BS=191;
const int MOD=1e9+7;
const int INV2=5e8+4;
const int HMOD=1004535809;
int n,qu,occ[MAXN+5][28],pw[MAXN+5],ipw[MAXN+5],pw_hs[MAXL+5];
char s[MAXM+5],t[MAXN+5];string str[22];
int getocc(string s,string t){
	static int hss[MAXL*2+5];int hst=0,res=0;
	for(int i=1;i<=s.size();i++) hss[i]=(1ll*hss[i-1]*BS+s[i-1])%HMOD;
	for(int i=0;i