0 like 0 dislike
656 views
| 656 views

0 like 0 dislike
```You are given a string A. You need to solve Q queries. In each queries, you will be given a string B[i].

you need to find the count of the number of substrings of A which are anagrams of B[i].

Contraints:
1<=|A|, |B[i]|<=10^5
1<=Q<=10^5
summation|B[i]|<=2x10^5
All the strings consists of lowercase english letters.

Input1:
A: jdlidfa
B: [ "daf", "ifd", "dxzjbltsmufythgm"]

Output2:
[1, 1, 0]

Input2:
A: "lrprpqejhh"
B: [ "p", "pjeplqrr"]

Output2:
[2, 0]

This is my Approach which is partially accepted ):
#include<bits/stdc++.h>
int fun(string s,string p)
{
int ans=0,matchsize=p.size(),l=0,r=0,n=s.size();
if(matchsize>n)
return ans;
vector<int> target(26,0);
for(char c:p)
{
target[c-'a']++;
}
while(r<n)
{
char c=s[r];
if(target[c-'a']>0)
--matchsize;
--target[c-'a'];

if(r-l+1==p.size())
{
if(matchsize==0)
{
ans++;
}
char begin_c=s[l];
if(target[begin_c-'a']>=0)
++matchsize;

++target[begin_c-'a'];
++l;
}
++r;
}
return ans;

}
vector<int> Solution::solve(string s, vector<string> &B)
{
int n=B.size(),i;
vector<int> ans(n,0);
for(i=0;i<n;i++)
{
ans[i]=fun(s,B[i]);
}
return ans;
}```
by Expert (111,330 points)