自动搬运

查看原文

来自洛谷，原作者为

	Zhao_daodao 赛场上要敢想，敢写

搬运于2025-08-24 22:59:47，当前版本为作者最后更新于2024-09-26 14:47:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

「BZOJ 2372」music

模拟赛 T2，被各位大神爆切。

Description

给你一个长度为 $n$ 的序列 S，一个长度为 $m$ 的序列 T。序列的数是 $[1,x]$ 之间的正整数。

定义两个长度相等的串等价：在这两个串中相对顺序不变。如 aabcd 和 iixyz 就是等价的。

问在 S 中，有多少个子串跟 T 等价，并按顺序输出。

$1\le n\le 10^5,1\le m\le 25000,1\le x\le 25$。

Solution

发现字符集大小为一个常数，跟字符串中的小写字母很像。可以考虑一些字符串的做法。

相对顺序不变很不好判断。没有什么 DS 可以维护这种东西。

在 S 中，可能跟 T 等价的子串长度一定为 $m$。所以事实上需要判断的串只有 $O(n)$ 个。

考虑直接暴力统计每一个序列的数的 rk，最后暴力判断。

想到这里差不多就做完了。

类似字符串 hash 的做法。记 字符 $x$ 的 hash 值为 $hsh_x$。

因为每一个字符对应的 rk 可能不一样，所以直接每一个字符存一个数。

什么意思呢，如果串是 abccb，那么在 a 中，就存下 10000，b 中存 1001，c 中存 110。

最后整一个串的 hash 值就是 $\sum hsh_x \times rk_x$。

从左到右扫，记录当前区间每一个字符的出现次数。出现过就给它一个 rank。每一次都重新扫。

每一次对于每一个 hash 值，$hsh_x\leftarrow hsh_x\times base$。当前位置的 hash 值就额外加 1。

如果要删除一个字符，$hsh_x\leftarrow hsh_x-base^m$。

再以 T 做同样的事情，直接判断 T 的 hash 值和 $\sum hsh_x\times rk_x$ 就可以了。

复杂度 $O((n+m)s)$。

Code

#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int MAXN=1e6+5;
const int base=19260817;
int n,m,s;
int S[MAXN],T[MAXN];
ll fc[MAXN];
int cnt2[27],id2[27],tot2;
int cnt1[27],id[27],tot1;
ll num[27];
inline void add(int x,bool need){num[x]=(num[x]*base+need);}
inline void del(int x){num[x]=(num[x]-fc[m]);}
inline void make_hsh(){tot1=0;for(int i=1;i<=s;i++)if(cnt1[i])id[i]=++tot1;}
inline ll hsh(){
	ll ans=0;
	for(int i=1;i<=s;i++)ans+=num[i]*id[i];
	return ans;
}
ll hsh2;
inline void init(){
	fc[0]=1;
    for(int i=1;i<=max(n,m);i++)fc[i]=fc[i-1]*base;
	for(int i=1;i<=m;i++)cnt2[T[i]]++;
	for(int i=1;i<=s;i++)if(cnt2[i])id2[i]=++tot2;
	for(int i=1;i<=m;i++)hsh2=(hsh2*base+id2[T[i]]);
}
signed main(){
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>m>>s;
    for(int i=1;i<=n;i++)cin>>S[i];
    for(int i=1;i<=m;i++)cin>>T[i];
	vector<int>ans;
    init();
	for(int i=1;i<=n;i++){
		for(int x=1;x<=s;x++)add(x,S[i]==x);
		cnt1[S[i]]++;
		if(i>m){del(S[i-m]);cnt1[S[i-m]]--;}
		if(i>=m){
			make_hsh();
			if(hsh()==hsh2)ans.push_back(i);
		}
	}
	cout<<ans.size()<<"\n";
	for(int i:ans)cout<<i-m+1<<"\n";
}