Acwing秋季每日一题补题---搜索字符串

搜索字符串

题目链接

思路：

字符串哈希+滑动窗口
当然因为符合题意的子串会重复，所以我们要考虑去重的问题

代码：

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long

const int N=2e5+10;
const int P=131;

char a[N],b[N];//字符串
int cnt[26];//统计字符个数
int  h[N],p[N];//hash，离散化

int get(int l,int r){
	return h[r]-h[l-1]*p[r-l+1];
}

void solve(){
	scanf("%s%s",a+1,b+1);
	int n=strlen(a+1);
	int m=strlen(b+1);
	p[0]=1;
	for(int i=1;i<=m;i++){
		p[i]=p[i-1]*P;
		h[i]=h[i-1]*P+b[i];
	}//对字符串b进行离散化(hash)

	for(int i=1;i<=n;i++){
		cnt[a[i]-'a']++;

	}

	int t=0;
	unordered_set<int> hash;

	for(int i=0;i<26;i++){
		if(!cnt[i]){
			t++;
		}
	}
	for(int i=1;i<=m;i++){
		int x=b[i]-'a';
		cnt[x]--;
		if(cnt[x]==0){
			t++;

		}
		else if(cnt[x]==-1){
			t--;

		}
		if(i>n){
			int s=b[i-n]-'a';
			cnt[s]++;
			if(cnt[s]==0){
				t++;

			}
			else if(cnt[s]==1){
				t--;

			}
		}
		if(t==26){
			hash.insert(get(i-n+1,i));

		}
	}
	cout<<hash.size()<<endl;
	return ;
	

}

signed main(){
	int t=1;
	while(t--){
		solve();
	}
	return 0;

}