is_permutation() en C++ y su aplicación para la búsqueda de anagramas

is_permutations() se usa para verificar si dos contenedores como string y vector son una permutación entre sí. Acepta tres parámetros, los primeros dos parámetros son las posiciones inicial y final del primer objeto y el tercer parámetro es la posición inicial del segundo objeto.
 

// C++ program to demonstrate working of
// is_permutation()
#include <bits/stdc++.h>
using namespace std;
 
// Driver program to test above
int main()
{
    vector<int> v1{1, 2, 3, 4};
    vector<int> v2{2, 3, 1, 4};
 
    // v1 and v2 are permutation of each other
    if (is_permutation(v1.begin(), v1.end(), v2.begin()))
        cout << "True\n";
    else
        cout << "False\n";
 
    // v1 and v3 are NOT permutation of each other
    vector<int> v3{5, 3, 1, 4};
    if (is_permutation(v1.begin(), v1.end(), v3.begin()))
        cout << "True\n";
    else
        cout << "False\n";
 
    return 0;
}

Producción : 

True
False

 
Aplicación: 
dado un patrón y un texto, encuentre todas las ocurrencias del patrón y sus anagramas en el texto.
Ejemplos: 
 

Input : text ="forxxorfxdofr"  
        pat = "for"
Output :  3
There are three anagrams of "for"
int text.

Input : word = "aabaabaa" 
        text = "aaba"
Output : 4

Hemos discutido una (n) solución para ella . Pero en esta publicación se hace usando is_permutation(). Aunque la complejidad es mayor que el método discutido anteriormente , el propósito es explicar la aplicación de is_permutation().
Deje que el tamaño del patrón a buscar sea pat_len. La idea es atravesar el texto dado y para cada ventana de tamaño pat_len, verificar si es una permutación del patrón dado o no.
 

// C++ program to count all permutation of
// given text
#include<bits/stdc++.h>
using namespace std;
 
// Function to count occurrences of anagrams of pat
int countAnagrams(string text, string pat)
{
    int t_len = text.length();
    int p_len = pat.length();
 
    // Start traversing the text
    int count = 0; // Initialize result
    for (int i=0; i<=t_len-p_len; i++)
 
        // Check if substring text[i..i+p_len]
        // is a permutation of pat[].
        // Three parameters are :
        // 1) Beginning position of current window in text
        // 2) End position of current window in text
        // 3) Pattern to be matched with current window
        if (is_permutation(text.begin()+i,
                           text.begin()+i+p_len,
                           pat.begin()))
            count++;
 
    return count;
}
 
// Driver code
int main()
{
    string str = "forxxorfxdofr";
    string pat = "for";
    cout << countAnagrams(str, pat) << endl;
    return 0;
}

Producción: 
 

3

Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.