1. Set count=0;
For i=0:i<a.length()-b.length()+1
IF (check(a.substr(i,b.length()),b))
count++;
2. Print count
So the idea is pretty simple. What we are doing is to slide the window and check for anagrams. Window is nothing but the substring being extracted every time. Window length is equal to the word length.
To check anagrams
FUNCTION check(string a, string b)
1. Declare a map <char, int="" style="box-sizing: border-box;"> m; //to store frequency of each character
2. For string abuild the map
For (int i=0;i<a.length();i++)
m[a[i]]++;
END FOR
3. For string bdestruct the map.
For (int i=0;i<b.length();i++)
m[b[i]]--;
END FOR
4. If map is totally destructed that means all key has value perfectly 0
return true;
Else
Return false.
END FUNCTION
</char,>
So this basically means, we are constructing a container using the elements of string a. Then we are destructing the map to form string b. If such formation is possible they strings are anagrams of each other.
C++ implementation:
#include <bits/stdc++.h>
using namespace std;
bool check(string a,string b){
//checking anagrams
map<char,int> m;
for(int i=0;i<a.length();i++)
m[a[i]]++;
for(int i=0;i<b.length();i++)
m[b[i]]--;
for(auto it=m.begin();it!=m.end();it++)
if(it->second!=0)
return false;
return true;
}
int countNoOfAnagram(string a,string b){
int count=0;
//sliding window
for(int i=0;i<a.length()-b.length()+1;i++){
if(check(a.substr(i,b.length()),b))
count++;
}
return count;
}
int main()
{
string S,C;
cout<<"Enter string S and word C\n";
cin>>S>>C;
cout<<"No of anagrams: "countNoOfAnagram(S,C)<<endl;
return 0;
}
Output
Enter string S and word C
fororfrdofr
for
No of anagrams: 3
Algorithm:
So the idea is pretty simple. What we are doing is to slide the window and check for anagrams. Window is nothing but the substring being extracted every time. Window length is equal to the word length.
To check anagrams
So this basically means, we are constructing a container using the elements of string a. Then we are destructing the map to form string b. If such formation is possible they strings are anagrams of each other.
C++ implementation:
Output
need an explanation for this answer? contact us directly to get an explanation for this answer