Count of anagrams of a text in a given string

Question

Problem Statement:

Given a word and a text, return the count of the occurences of anagrams of the word in the text. For eg. word is "for" and the text is "forxxorfxdofr", anagrams of "for" will be "ofr", "orf","fro", etc. So the answer would be 3 for this particular example.

The above is an interview question I saw here.

Here is the code I have written:

#include <iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int equals(char* A, char* B)
{
 int i,len = strlen(A);
 int a[26],b[26];
 for(i=0;i<26;i++)
 {
 a[i]=0;
 b[i]=0;
 }
 for(i=0;i<len;i++)
 {
 a[A[i]-'a']++;
 }
 for(i=0;i<len;i++)
 {
 b[B[i]-'a']++;
 }
 for(i=0;i<26;i++)
 {
 if(a[i]!=b[i])
 return 0;
 }
 return 1;
}
int check(char* s1, char* s2)
{
 int i,j,len1=strlen(s1), len2=strlen(s2), flag=0;
 char arr[len2];
 for(i=0;i<=len1-len2;i++)
 {
 for(j=0;j<len2;j++)
 {
 arr[j]=s1[i+j];
 }
 if(equals(arr,s2))
 flag++;
 }
 return flag;
}
int main()
{
 char text[50]="",pat[50]="";
 cout<<"Enter original string: ";
 cin>>text;
 cout<<"Enter pattern string: ";
 cin>>pat;
 cout<<"No. of anagrams in text are :"<<check(text,pat);
 return 0;
}

(I have also mentioned this code in my technical blog).

Questions:

1. How can I improve my code in terms of its complexity and efficiency? As of now, it uses an approach similar to the naive string matching algorithm.
2. Is my method to not compute all permutations and instead use an array good enough, or are there any better approaches?

Answer 1

You code is quite efficient and well designed. I think you can get a little bit more efficiency at the cost of making the code more specific to this particular task. In particular there are some shortcuts:

1. your pattern is always the same so you could cache the computation of the array b[26]. This would double the speed

2. when you fill array a[] you could stop whenever a[i]>b[i]. This could speed up your algorithm a lot in some scenarios. For example you skip a position at once if the letter in the text is not in the pattern.

3. you are making copies of strings just to add the null terminator. You can avoid this by adding the length of the string as a parameter to your first function. This would help point 2 to be quite fast in the scenario already mentioned.

4. you can update the array a[26] incrementally. You decrease the count of character which exit the window and increment the count of characters entering it.

Putting all together (not tested):

int check(const char *text, const char *pattern) {
 int pattern_frequency[26];
 int text_frequency[26];
 int matches = 0;
 int pattern_length;
 for (int i=0; i<26; ++i) {
 pattern_frequency[i] = 0;
 text_frequency[i] = 0;
 }
 for (pattern_length=0; pattern[pattern_length]; ++pattern_length) {
 int i = pattern[pattern_length]-'a';
 assert(i>=0 && i<26);
 pattern_frequency[i]++; 
 }
 for (int i=0; text[i]; ++i) {
 if (i>=pattern_length) {
 text_frequency[text[i-pattern_length]-'a']--;
 }
 int c = text[i]-'a';
 assert(c>=0 && c<26);
 text_frequency[c]++;
 if (text_frequency[c] != pattern_frequency[c]) continue; // shortcut
 int j;
 for (j=0;j<26 && text_frequency[j]==pattern_frequency[j];++j);
 if (j<26) continue;
 matches ++;
 } 
 return matches;
}

If n is the length of the text and m the length of the pattern, your algorithm is O(nm) while this one is O(n+m) which cannot be improved further.

• CyberLingo: What is assert in assert(i>=0 && i<26);
• Emanuele Paolini: gnu.org/software/libc/manual/html_node/…
• CyberLingo: Thank you! I removed the assert function and it's working fine as well.