Frecuencia de una string en una array de strings

Se le proporciona una colección de strings y una lista de consultas. Para cada consulta hay una string dada. Necesitamos imprimir el número de veces que aparece la string dada en la colección de strings. 

Ejemplos: 

Input : arr[] = {wer, wer, tyu, oio, tyu}
        q[] =   {wer, tyu, uio}
Output : 2 2 0
Explanation : 
q[0] appears two times in arr[], q1[] appears

Método 1 (Simple)

La idea es simple, para cada string de consulta la comparamos con todas las strings dadas en la array. Si la string de consulta coincide, incrementamos el conteo. 

// C++ program to find number of times a
// string appears in an array.
#include<bits/stdc++.h>
using namespace std;
 
// Returns count of occurrences of s in arr[]
int search(string arr[], string s, int n)
{
    int counter = 0;
 
    for(int j = 0; j < n; j++)
     
        // Checking if string given in query
        // is present in the given string.
        // If present, increase times
        if (s == arr[j])
            counter++;
 
   return counter;
}
  
void answerQueries(string arr[], string q[],
                   int n, int m)
{
    for(int i = 0; i < m; i++)
        cout << search(arr, q[i], n) << " ";
}   
 
// Driver Code
int main()
{
    string arr[] = { "aba", "baba",
                     "aba", "xzxb" };
    string q[]   = { "aba", "xzxb", "ab" };
     
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = sizeof(q) / sizeof(q[0]);
     
    answerQueries(arr, q, n, m);
}
 
// This code is contributed by rutvik_56

// Java program to find number of times a string
// appears in an array.
class SubString
{
    /* Returns count of occurrences of s in arr[] */
    static int search(String[]arr, String s)
    {
            int counter = 0;
            for (int j = 0; j < arr.length; j++)
 
                /* checking if string given in query is
                  present in the given string. If present,
                  increase times*/
                if (s.equals(arr[j]))
                    counter++;
 
           return counter;
    }
 
    static void answerQueries(String[] arr, String q[])
    {
        for (int i=0;i<q.length; i++)
            System.out.print(search(arr, q[i]) + " ");
    }
 
    /* driver code*/
    public static void main(String[] args) {
 
        String[] arr = {"aba","baba","aba","xzxb"};
        String[] q   = {"aba","xzxb","ab"};
        answerQueries(arr, q);
    }
}

# Python3 program to find number of
# times a string appears in an array.
 
# Returns count of occurrences of s in arr[]
def search(arr, s):
    counter = 0
    for j in range(len(arr)):
         
        # checking if string given in query
        # is present in the given string. 
        # If present, increase times
        if (s == (arr[j])):
            counter += 1
 
    return counter
 
def answerQueries(arr, q):
    for i in range(len(q)):
        print(search(arr, q[i]),
                     end = " ")
 
# Driver code
if __name__ == '__main__':
    arr = ["aba", "baba", "aba", "xzxb"]
    q = ["aba", "xzxb", "ab"]
    answerQueries(arr, q)
 
# This code is contributed
# by PrinciRaj19992

// C# program to find number of
// times a string appears in an array.
using System;
 
class SubString
{
    /* Returns count of occurrences of s in arr[] */
    static int search(String[]arr, String s)
    {
            int counter = 0;
            for (int j = 0; j < arr.Length; j++)
 
                /* checking if string given in query is
                present in the given string. If present,
                increase times*/
                if (s.Equals(arr[j]))
                    counter++;
 
        return counter;
    }
 
    static void answerQueries(String []arr, String []q)
    {
        for (int i = 0; i < q.Length; i++)
            Console.Write(search(arr, q[i]) + " ");
    }
 
    // Driver code
    public static void Main()
    {
        String []arr = {"aba","baba","aba","xzxb"};
        String []q = {"aba","xzxb","ab"};
        answerQueries(arr, q);
    }
}
 
//This code is contributed by nitin mittal

<?php
# Php program to find number of
# times a string appears in an array.
 
# Returns count of occurrences of s in arr[]
function search($arr, $s)
{
    $counter = 0;
    for ($j=0; $j<count($arr); $j++)
    {
        # checking if string given in query
        # is present in the given string.
        # If present, increase times
        if ($s == ($arr[$j]))
            $counter += 1;
    }
    return $counter;
}
function answerQueries($arr, $q)
{
    for ($i=0; $i<count($q); $i++)
    {
        echo(search($arr, $q[$i]));
        echo (" ");
    }
}
 
# Driver code
 
$arr = array("aba", "baba", "aba", "xzxb");
$q = array("aba", "xzxb", "ab");
answerQueries($arr, $q);
 
# This code is contributed
# by Shivi_Aggarwal
?>

<script>
// javascript program to find number of times a string
// appears in an array.
    /* Returns count of occurrences of s in arr */
    function search( arr,  s) {
        var counter = 0;
        for (j = 0; j < arr.length; j++)
 
            /*
             * checking if string given in query is present in the given string. If present,
             * increase times
             */
            if (s === (arr[j]))
                counter++;
 
        return counter;
    }
 
    function answerQueries( arr,  q) {
        for (i = 0; i < q.length; i++)
            document.write(search(arr, q[i]) + " ");
    }
 
    /* driver code */
        var arr = [ "aba", "baba", "aba", "xzxb" ];
        var q = [ "aba", "xzxb", "ab" ];
        answerQueries(arr, q);
 
// This code is contributed by gauravrajput1
</script>

2 1 0 

Método 2 (usando Trie)

Pruebe una estructura de datos eficiente utilizada para el almacenamiento y la recuperación de datos como strings. La complejidad de búsqueda es óptima como longitud de clave. 
En esta solución, insertamos la colección de strings en la estructura de datos Trie para que se almacenen en ella. Una cosa importante es que llevamos la cuenta de las ocurrencias en los Nodes hoja. Luego buscamos en el Trie la string de consulta dada y verificamos si está presente en el Trie. 

// C++ program to count number of times
// a string appears in an array of strings
#include<iostream>
using namespace std;
 
const int MAX_CHAR = 26;
 
struct Trie
{
    // To store number of times
    // a string is present. It is
    // 0 is string is not present
    int cnt;
 
    Trie *node[MAX_CHAR];
    Trie()
    {
        for(int i=0; i<MAX_CHAR; i++)
            node[i] = NULL;
        cnt = 0;
    }
};
 
/* function to insert a string into the Trie*/
Trie *insert(Trie *root,string s)
{
    Trie *temp = root;
    int n = s.size();
    for(int i=0; i<n; i++)
    {
        /*calculation ascii value*/
        int index = s[i]-'a';
 
        /* If the given node is not already
          present in the Trie than create
          the new node*/
        if (!root->node[index])
            root->node[index] = new Trie();
 
        root = root->node[index];
    }
    root->cnt++;
    return temp;
}
 
/* Returns count of occurrences of s in Trie*/
int search(Trie *root, string s)
{
    int n = s.size();
    for (int i=0; i<n; i++)
    {
        int index = s[i]-'a';
        if (!root->node[index])
            return 0;
        root = root->node[index];
    }
    return root->cnt;
}
 
void answerQueries(string arr[], int n, string q[],
                                           int m)
{
    Trie *root = new Trie();
 
    /* inserting in Trie */
    for (int i=0; i<n; i++)
        root = insert(root,arr[i]);
 
    /* searching the strings in Trie */
    for (int i=0; i<m; i++)
        cout << search(root, q[i]) << " ";
 
}
 
/* Driver code */
int main()
{
    string arr[] = {"aba","baba","aba","xzxb"};
    int n = sizeof(arr)/sizeof(arr[0]);
 
    string q[] = {"aba","xzxb","ab"};
    int m = sizeof(q)/sizeof(q[0]);
 
    answerQueries(arr, n, q, m);
 
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.*;
 
class GFG
{
   
// Java program to count number of times
// a string appears in an array of string
 
static int MAX_CHAR = 26;
 
static class Trie
{
    // To store number of times
    // a string is present. It is
    // 0 is string is not present
    public int cnt;
 
    public Trie node[] = new Trie[MAX_CHAR];
    public Trie()
    {
        for(int i=0; i<MAX_CHAR; i++)
            node[i] = null;
        cnt = 0;
    }
}
 
/* function to insert a string into the Trie*/
static Trie insert(Trie root,String s)
{
    Trie temp = root;
    int n = s.length();
    for(int i=0; i<n; i++)
    {
        /*calculation ascii value*/
        int index = (int)s.charAt(i) - (int)'a';
 
        /* If the given node is not already
          present in the Trie than create
          the new node*/
        if (root.node[index] == null)
            root.node[index] = new Trie();
 
        root = root.node[index];
    }
    root.cnt++;
    return temp;
}
 
/* Returns count of occurrences of s in Trie*/
static int search(Trie root, String s)
{
    int n = s.length();
    for (int i=0; i<n; i++)
    {
        int index = (int)s.charAt(i) - (int)'a';
        if (root.node[index] == null)
            return 0;
        root = root.node[index];
    }
    return root.cnt;
}
 
static void answerQueries(String arr[], int n, String q[],
                                           int m)
{
    Trie root = new Trie();
 
    /* inserting in Trie */
    for (int i=0; i<n; i++)
        root = insert(root,arr[i]);
 
    /* searching the Strings in Trie */
    for (int i=0; i<m; i++)
        System.out.print(search(root, q[i]) + " ");
 
}
 
// Driver Code
public static void main(String args[])
{
    String arr[] = {"aba","baba","aba","xzxb"};
    int n = arr.length;
 
    String q[] = {"aba","xzxb","ab"};
    int m = q.length;
 
    answerQueries(arr, n, q, m);
}
}
 
// This code is contributed by shinjanpatra

# Python3 program to count number of times
# a string appears in an array of strings
MAX_CHAR = 26
 
class Trie:
 
    # To store number of times
    # a string is present. It is
    # 0 is string is not present
    def __init__(self):
        self.cnt = 0
        self.node = [None for i in range(MAX_CHAR)]
 
# function to insert a string into the Trie
def insert(root, s):
    temp = root
    n = len(s)
     
    for i in range(n):
 
        # calculation ascii value
        index = ord(s[i]) - ord('a')
 
        ''' If the given node is not already
        present in the Trie than create
        the new node '''
        if (not root.node[index]):
            root.node[index] = Trie()
        root = root.node[index]   
    root.cnt += 1   
    return temp
 
# Returns count of occurrences of s in Trie
def search( root, s):
    n = len(s)
     
    for i in range(n):   
        index = ord(s[i]) - ord('a')
        if (not root.node[index]):
            return 0
        root = root.node[index]   
    return root.cnt
 
def answerQueries(arr, n, q, m):
 
    root = Trie()
 
    # inserting in Trie
    for i in range(n):
        root = insert(root, arr[i])
 
    # searching the strings in Trie
    for i in range(m):
        print(search(root, q[i]))
 
# Driver code
if __name__=='__main__':
 
    arr = ["aba", "baba", "aba", "xzxb"]
    n = len(arr)
 
    q = ["aba", "xzxb", "ab"]
    m = len(q)
 
    answerQueries(arr, n, q, m)
 
    # This code is contributed by pratham76

<script>
 
// JavaScript program to count number of times
// a string appears in an array of strings
const MAX_CHAR = 26
 
class Trie{
 
    // To store number of times
    // a string is present. It is
    // 0 is string is not present
    constructor(){
        this.cnt = 0
        this.node = new Array(MAX_CHAR).fill(null)
    }
}
 
// function to insert a string into the Trie
function insert(root, s){
    let temp = root
    let n = s.length
     
    for(let i=0;i<n;i++){
 
        // calculation ascii value
        let index = s.charCodeAt(i) - 'a'.charCodeAt(0)
 
        // If the given node is not already
        // present in the Trie than create
        // the new node
 
        if (!root.node[index]){
            root.node[index] = new Trie()
        }
        root = root.node[index]
    }
    root.cnt += 1
    return temp
}
 
// Returns count of occurrences of s in Trie
function search(root,s){
    let n = s.length
     
    for(let i=0;i<n;i++){
        let index = s.charCodeAt(i) - 'a'.charCodeAt(0)
        if (!root.node[index])
            return 0
        root = root.node[index]
    }
    return root.cnt
}
 
function answerQueries(arr, n, q, m){
 
    let root = new Trie()
 
    // inserting in Trie
    for(let i = 0; i < n; i++){
        root = insert(root, arr[i])
    }
 
    // searching the strings in Trie
    for(let i = 0; i < m; i++){
        document.write(search(root, q[i]),"</br>")
    }
}
 
// Driver code
 
let arr = ["aba", "baba", "aba", "xzxb"]
let n = arr.length
 
let q = ["aba", "xzxb", "ab"]
let m = q.length
 
answerQueries(arr, n, q, m)
 
// This code is contributed by shinjanpatra
 
</script>

2 1 0 

Método 3 (Hashing)

Podemos usar un mapa hash e insertar todas las strings dadas en él. Para cada string de consulta, simplemente hacemos una búsqueda en el mapa hash.
Consulte la estructura de datos para el diccionario para comparar las soluciones basadas en hashing y Trie.

Este artículo es una contribución de Pranav . 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.