forked from Vishal-Aggarwal0305/DSA
-
Notifications
You must be signed in to change notification settings - Fork 0
/
countAnagrams.cpp
51 lines (38 loc) · 857 Bytes
/
countAnagrams.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
long long countAnagrams(string s, string ana){
unordered_map<char, int> m;
for(auto it : ana) m[it]++;
int k=ana.length();
int count=m.size();
int i=0, j=0;
long long ans=0;
while(j<s.length()){
if(m.find(s[j])!=m.end()){
m[s[j]]--;
if(m[s[j]]==0) count--;
}
if((j-i+1)<k) j++;
else if((j-i+1)==k){
if(count==0) ans++;
if(m.find(s[i])!=m.end()){
m[s[i]]++;
if(m[s[i]]==1) count++;
}
i++;
j++;
}
}
return ans;
}
int main() {
int t;
cin>>t;
while(t--){
string s, txt;
cin>>s>>txt;
long long ans = countAnagrams(s, txt);
cout<<ans<<endl;
}
return 0;
}