题解：P10634 BZOJ2372 music
Zhao_daodao
·
·
题解
「BZOJ 2372」music
模拟赛 T2，被各位大神爆切。
Description
给你一个长度为 n 的序列 S，一个长度为 m 的序列 T。序列的数是 [1,x] 之间的正整数。
定义两个长度相等的串等价：在这两个串中相对顺序不变。如 aabcd 和 iixyz 就是等价的。
问在 S 中，有多少个子串跟 T 等价，并按顺序输出。
## 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
```cpp
#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";
}
```