求调

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1000005;
const ull bs=131;
int T;
string s,t;
ull pb[N],hs[5][N];
map<char,int>mp;
int st[N],tt[N];
ull get(int i,int l,int r){
	if(l>r) return 0;
	return hs[i][r]-hs[i][l-1]*pb[r-l+1];
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	pb[0]=1;
	for(int i=1;i<N;i++) pb[i]=pb[i-1]*bs;
	cin>>T;
	while(T--){
		cin>>s>>t;
		int ss=s.size(),ts=t.size();
		s=' '+s;t=' '+t;
		for(int i=1;i<=ss;i++){
			if(s[i]>'Z') hs[1][i]=hs[1][i-1]*bs;
			else hs[1][i]=hs[1][i-1]*bs+s[i];
		}
		for(int i=1;i<=ts;i++){
			if(t[i]>'Z') hs[2][i]=hs[2][i-1]*bs;
			else hs[2][i]=hs[2][i-1]*bs+t[i];
		}
		mp.clear();
		for(int i=1;i<=ss;i++){
			st[i]=0;
			if(s[i]<='Z') continue;
			if(mp[s[i]])st[i]=i-mp[s[i]];
			mp[s[i]]=i;
		}
		mp.clear();
		for(int i=1;i<=ts;i++){
			tt[i]=0;
			if(t[i]<='Z') continue;
			if(mp[t[i]])tt[i]=i-mp[t[i]];
			mp[t[i]]=i;
		}
		for(int i=1;i<=ss;i++){
			hs[3][i]=hs[3][i-1]*bs+st[i];
		}
		for(int i=1;i<=ts;i++){
			hs[4][i]=hs[4][i-1]*bs+tt[i];
		}
		int fst=1,ans=0;
		for(int i=1;i+ts-1<=ss;i++){
			fst=max(fst,i);
			while(fst<=ss&&s[fst]<='Z') fst++;
			if(get(1,i,i+ts-1)!=get(2,1,ts)) continue;
			if(i+ts-1<fst||get(3,fst+1,i+ts-1)==get(4,fst-i+1,ts)){
				ans++;
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}