Contar las ocurrencias de anagramas

Dada una palabra y un texto, devuelve el recuento de las apariciones de anagramas de la palabra en el texto (por ejemplo: anagramas de palabra para son para, ofr, rof, etc.))

Ejemplos: 

Input : forxxorfxdofr
        for
Output : 3
Explanation : Anagrams of the word for - for, orf, 
ofr appear in the text and hence the count is 3.

Input : aabaabaa
        aaba
Output : 4
Explanation : Anagrams of the word aaba - aaba, 
abaa each appear twice in the text and hence the
count is 4.

Un enfoque simple es recorrer desde el inicio de la string considerando substrings de longitud igual a la longitud de la palabra dada y luego verificar si esta substring tiene todos los caracteres de la palabra.

// A Simple C++ program to count anagrams of a
// pattern in a text.
#include<bits/stdc++.h>
using namespace std;
 
// Function to find if two strings are equal
bool areAnagram(string s1, string s2)
{
    map<char, int> m;
    for(int i = 0; i < s1.length(); i++)
        m[s1[i]]++;
         
    for(int i = 0; i < s2.length(); i++)
        m[s2[i]]--;
         
    for(auto it = m.begin(); it != m.end(); it++)
        if(it -> second != 0)
            return false;
             
        return true;
}
 
int countAnagrams(string text, string word)
{
     
    // Initialize result
    int res = 0;
    for(int i = 0;
            i < text.length() - word.length() + 1;
            i++)
    {
         
        // Check if the word and substring are
        // anagram of each other.
        if (areAnagram(text.substr(i, word.length()),
                                      word))
            res++;
    }
    return res;
}
 
// Driver Code
int main()
{
    string text = "forxxorfxdofr";
    string word = "for";
     
    cout << countAnagrams(text, word);
     
    return 0;
}
 
// This code is contributed by probinsah

// A Simple Java program to count anagrams of a
// pattern in a text.
import java.io.*;
import java.util.*;
 
public class GFG {
 
    // Function to find if two strings are equal
    static boolean araAnagram(String s1,
                              String s2)
    {
        // converting strings to char arrays
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
 
        // sorting both char arrays
        Arrays.sort(ch1);
        Arrays.sort(ch2);
 
        // Check for equality of strings
        if (Arrays.equals(ch1, ch2))
            return true;
        else
            return false;
    }
 
    static int countAnagrams(String text, String word)
    {
        int N = text.length();
        int n = word.length();
 
        // Initialize result
        int res = 0;
 
        for (int i = 0; i <= N - n; i++) {
 
            String s = text.substring(i, i + n);
 
            // Check if the word and substring are
            // anagram of each other.
            if (araAnagram(word, s))
                res++;
        }
     
        return res;
    }
 
    // Driver code
    public static void main(String args[])
    {
        String text = "forxxorfxdofr";
        String word = "for";
        System.out.print(countAnagrams(text, word));
    }
}

# A Simple Python program to count anagrams of a
# pattern in a text.
 
# Function to find if two strings are equal
def areAnagram(s1, s2):
    m = {}
    for i in range(len(s1)):
        if s1[i] not in m:
            m[s1[i]] = 1
        else:
            cnt = m[s1[i]]
            m.pop(s1[i])
            m[s1[i]] = cnt + 1
 
    for j in range(len(s2)):
        if((s2[j] in m) == False):
            return False
        else:
            cnt = m[s2[j]]
            m.pop(s2[j])
            m[s2[j]] = cnt - 1
         
    for it in m.values():
       if(it != 0):
          return False
    return True
 
def countAnagrams(text, word):
     
    # Initialize result
    res = 0
    for i in range(len(text)- len(word)+1):
         
        # Check if the word and substring are
        # anagram of each other.
 
        if (areAnagram(text[i:i+len(word)], word)):
            res += 1
    return res
 
# Driver Code
 
text = "forxxorfxdofr"
word = "for"
     
print(countAnagrams(text, word))
 
# This code is contributed by shinjanpatra

<script>// A Simple JavaScript program to count anagrams of a
// pattern in a text.
 
// Function to find if two strings are equal
function areAnagram(s1, s2)
{
    let m = new Map();
    for(let i = 0; i < s1.length ; i++)
    {
        if(m.has(s1[i])===false){
            m.set(s1[i],1)
        }
        else{
            let cnt = m.get(s1[i]);
            m.delete(s1[i]);
            m.set(s1[i],cnt+1);
        }
    }
 
    for(let j = 0; j < s1.length; j++)
    {
        if(m.has(s2[j])===false){
            return false;
        }
        else{
            let cnt = m.get(s2[j]);
            m.delete(s2[j]);
            m.set(s2[j],cnt-1);
        }
    }
         
    for(const it in m.values()){
       if(it !== 0)return false
    }
    return true;
}
 
function countAnagrams(text, word)
{
     
    // Initialize result
    let res = 0;
    for(let i = 0;i < text.length - word.length + 1;i++)
    {
         
        // Check if the word and substring are
        // anagram of each other.
 
        if (areAnagram(text.substring(i, i+word.length), word)) res++;
    }
    return res;
}
 
// Driver Code
 
let text = "forxxorfxdofr";
let word = "for";
     
document.write(countAnagrams(text, word));
 
// This code is contributed by shinjanpatra
</script>

3

Complejidad del Tiempo: O(l1lognl1 + l2logl2)

Espacio auxiliar: O(l1 + l2). 

Una solución eficiente es usar la array de conteo para verificar los anagramas, podemos construir la ventana de conteo actual a partir de la ventana anterior en tiempo O (1) usando el concepto de ventana deslizante. 

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    static int findAnagrams(const std::string& text,
                            const std::string& word)
    {
        int text_length = text.length();
        int word_length = word.length();
        if (text_length < 0 || word_length < 0
            || text_length < word_length)
            return 0;
 
        constexpr int CHARACTERS = 256;
        int count = 0;
        int index = 0;
        std::array<char, CHARACTERS> wordArr;
        wordArr.fill(0);
        std::array<char, CHARACTERS> textArr;
        textArr.fill(0);
 
        // till window size
        for (; index < word_length; index++) {
            wordArr[CHARACTERS - word[index]]++;
            textArr[CHARACTERS - text[index]]++;
        }
        if (wordArr == textArr)
            count += 1;
        // next window
        for (; index < text_length; index++) {
            textArr[CHARACTERS - text[index]]++;
            textArr[CHARACTERS
                    - text[index - word_length]]--;
 
            if (wordArr == textArr)
                count += 1;
        }
        return count;
    }
};
 
int main()
{
    const std::string& text = "forxxorfxdofr";
    const std::string& word = "for";
 
    cout << Solution::findAnagrams(text, word);
    return 0;
}

// An efficient Java program to count anagrams of a
// pattern in a text.
import java.io.*;
import java.util.*;
 
class Solution {
    public static int countAnagrams(String s, String p)
    {
        // change CHARACTERS to support range of supported
        // characters
        int CHARACTERS = 256;
        int sn = s.length();
        int pn = p.length();
        int count = 0;
        if (sn < 0 || pn < 0 || sn < pn)
            return 0;
 
        char[] pArr = new char[CHARACTERS];
        char[] sArr = new char[CHARACTERS];
        int i = 0;
        // till window size
        for (; i < pn; i++) {
            sArr[CHARACTERS - s.charAt(i)]++;
            pArr[CHARACTERS - p.charAt(i)]++;
        }
        if (Arrays.equals(pArr, sArr))
            count += 1;
        // next window
        for (; i < sn; i++) {
            sArr[CHARACTERS - s.charAt(i)]++;
            sArr[CHARACTERS - s.charAt(i - pn)]--;
 
            if (Arrays.equals(pArr, sArr))
                count += 1;
        }
        return count;
    }
    // Driver code
    public static void main(String args[])
    {
        String text = "forxxorfxdofr";
        String word = "for";
        System.out.print(countAnagrams(text, word));
    }
}

# A Simple Python program to count anagrams of a
# pattern in a text with the help of sliding window problem
string = "forxxorfxdofr"
ptr = "for"
n = len(string)
k = len(ptr)
temp = []
d = {}
for i in ptr:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
i = 0
j = 0
count = len(d)
 
ans = 0
 
 
while j < n:
    if string[j] in d:
        d[string[j]] -= 1
        if d[string[j]] == 0:
            count -= 1
    if (j-i+1) < k:
        j += 1
    elif (j-i+1) == k:
        if count == 0:
            ans += 1
 
        if string[i] in d:
            d[string[i]] += 1
            if d[string[i]] == 1:
                count += 1
 
        i += 1
        j += 1
print(ans)

<script>
 
// A Simple JavaScript program to count anagrams of a
// pattern in a text with the help of sliding window problem
 
let string = "forxxorfxdofr"
let ptr = "for"
let n = string.length
let k = ptr.length
let temp = []
let d = new Map();
for(let i = 0; i < ptr.length; i++)
{
    if(d.has(ptr[i]))
        d.set(ptr[i], d.get(ptr[i])+1)
    else
        d.set(ptr[i], 1)
}
 
let i = 0
let j = 0
let count = d.size
 
let ans = 0
 
while(j < n)
{
    if(d.has(string[j]))
    {
        d.set(string[j], d.get(string[j]) - 1)
        if(d.get(string[j]) == 0)
            count--
    }
    if(j - i + 1 < k)
        j++
    else if(j - i + 1 == k){
        if(count == 0)
            ans++
 
        if(d.has(string[i]))
        {
            d.set(string[i],d.get(string[i])+1)
            if(d.get(string[i]) == 1)
                count++
        }
        i++
        j++
    }
}
 
document.write(ans)
 
// This code is contributed by shinjanpatra
 
</script>

3

Complejidad del Tiempo: O(l1 + l2)

Espacio auxiliar: O(l1 + l2). 

Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.