Acw 5220
题意
自己看
思路
假设串N长度为\(n\)，串H长度为\(m\)，遍历串H，对于\([i,i+n-1]\)这一段子串，如果所含字母个数与串N所含字母个数相同，则认为匹配，问题在于 如何判断 排列重合 的问题。字符串哈希。匹配的话直接将这一段的哈希值放入set中，去重，最后set的size就是答案
代码
const int N=1e6,M = 1e6,mod = 1e9+7,inf=1e18,P=1331;
//9.19
int n,m,k;
//字符串哈希
ull p[N],h[N];
string s,t;
int cnt[26];
ull get(int l,int r)
{
return h[r]-h[l-1]*p[r-l+1];
}
void solve()
{
cin>>s>>t;
n=s.size();
m=t.size();
s=" "+s;
t=" "+t;
//字符串哈希模板
p[0]=1;
for(int i=1;i<=m;i++)
{
p[i]=p[i-1]*P;
h[i]=h[i-1]*P+t[i];
}
unordered_set<ull> hash;
for(int i=1;i<=n;i++) cnt[s[i]-'a']++;
int ok=0;
for(int i=0;i<26;i++) ok+=(!cnt[i]);
for(int i=1;i<=m;i++)
{
int c=t[i]-'a';
cnt[c]--;
if(cnt[c]==0) ok++;
else if(cnt[c]==-1) ok--;
if(i>n)
{
cnt[t[i-n]-'a']++;
if(cnt[t[i-n]-'a']==0) ok++;
else if(cnt[t[i-n]-'a']==1) ok--;
}
if(ok==26)
{
hash.insert(get(i-n+1,i));
}
}
cout<<hash.size()<<endl;
}