Dadas dos strings, encuentre el número de veces que la segunda string ocurre en la primera string, ya sea continua o discontinua.
Ejemplos:
Input: string a = "GeeksforGeeks" string b = "Gks" Output: 4 Explanation: The four strings are - (Check characters marked in bold) GeeksforGeeks GeeksforGeeks GeeksforGeeks GeeksforGeeks
Si analizamos cuidadosamente el problema dado, podemos ver que se puede dividir fácilmente en subproblemas. La idea es procesar todos los caracteres de ambas strings uno por uno comenzando desde el lado izquierdo o derecho. Atravesemos desde la esquina derecha, hay dos posibilidades para cada par de caracteres atravesados.
m: Length of str1 (first string)
n: Length of str2 (second string)
If last characters of two strings are same,
1. We consider last characters and get count for remaining
strings. So we recur for lengths m-1 and n-1.
2. We can ignore last character of first string and
recurse for lengths m-1 and n.
else
If last characters are not same,
We ignore last character of first string and
recurse for lengths m-1 and n.
A continuación se muestra la implementación de la solución recursiva Naive anterior:
C++
// A Naive recursive C++ program to find the number of
// times the second string occurs in the first string,
// whether continuous or discontinuous
#include <iostream>
using namespace std;
// Recursive function to find the number of times
// the second string occurs in the first string,
// whether continuous or discontinuous
int count(string a, string b, int m, int n)
{
// If both first and second string is empty,
// or if second string is empty, return 1
if ((m == 0 && n == 0) || n == 0)
return 1;
// If only first string is empty and second
// string is not empty, return 0
if (m == 0)
return 0;
// If last characters are same
// Recur for remaining strings by
// 1. considering last characters of both strings
// 2. ignoring last character of first string
if (a[m - 1] == b[n - 1])
return count(a, b, m - 1, n - 1) +
count(a, b, m - 1, n);
else
// If last characters are different, ignore
// last char of first string and recur for
// remaining string
return count(a, b, m - 1, n);
}
// Driver code
int main()
{
string a = "GeeksforGeeks";
string b = "Gks";
cout << count(a, b, a.size(), b.size()) << endl;
return 0;
}
Java
// A Naive recursive java program to find the number of
// times the second string occurs in the first string,
// whether continuous or discontinuous
import java.io.*;
class GFG
{
// Recursive function to find the number of times
// the second string occurs in the first string,
// whether continuous or discontinuous
static int count(String a, String b, int m, int n)
{
// If both first and second string is empty,
// or if second string is empty, return 1
if ((m == 0 && n == 0) || n == 0)
return 1;
// If only first string is empty and
// second string is not empty, return 0
if (m == 0)
return 0;
// If last characters are same
// Recur for remaining strings by
// 1. considering last characters of
// both strings
// 2. ignoring last character of
// first string
if (a.charAt(m - 1) == b.charAt(n - 1))
return count(a, b, m - 1, n - 1) +
count(a, b, m - 1, n);
else
// If last characters are different,
// ignore last char of first string
// and recur for remaining string
return count(a, b, m - 1, n);
}
// Driver code
public static void main (String[] args)
{
String a = "GeeksforGeeks";
String b = "Gks";
System.out.println( count(a, b, a.length(), b.length())) ;
}
}
// This code is contributed by vt_m
Python 3
# A Naive recursive Python program # to find the number of times the # second string occurs in the first # string, whether continuous or # discontinuous # Recursive function to find the # number of times the second string # occurs in the first string, # whether continuous or discontinuous def count(a, b, m, n): # If both first and second string # is empty, or if second string # is empty, return 1 if ((m == 0 and n == 0) or n == 0): return 1 # If only first string is empty # and second string is not empty, # return 0 if (m == 0): return 0 # If last characters are same # Recur for remaining strings by # 1. considering last characters # of both strings # 2. ignoring last character # of first string if (a[m - 1] == b[n - 1]): return (count(a, b, m - 1, n - 1) + count(a, b, m - 1, n)) else: # If last characters are different, # ignore last char of first string # and recur for remaining string return count(a, b, m - 1, n) # Driver code a = "GeeksforGeeks" b = "Gks" print(count(a, b, len(a),len(b))) # This code is contributed by ash264
C#
// A Naive recursive C# program to find the number of
// times the second string occurs in the first string,
// whether continuous or discontinuous
using System;
class GFG
{
// Recursive function to find the number of times
// the second string occurs in the first string,
// whether continuous or discontinuous
static int count(string a, string b, int m, int n)
{
// If both first and second string is empty,
// or if second string is empty, return 1
if ((m == 0 && n == 0) || n == 0)
return 1;
// If only first string is empty and
// second string is not empty, return 0
if (m == 0)
return 0;
// If last characters are same
// Recur for remaining strings by
// 1. considering last characters of
// both strings
// 2. ignoring last character of
// first string
if (a[m - 1] == b[n - 1])
return count(a, b, m - 1, n - 1) +
count(a, b, m - 1, n);
else
// If last characters are different,
// ignore last char of first string
// and recur for remaining string
return count(a, b, m - 1, n);
}
// Driver code
public static void Main ()
{
string a = "GeeksforGeeks";
string b = "Gks";
Console.Write( count(a, b, a.Length, b.Length) );
}
}
// This code is contributed by nitin mittal
PHP
<?php
// A Naive recursive PHP program to find the number of
// times the second string occurs in the first string,
// whether continuous or discontinuous
// Recursive function to find the number of times
// the second string occurs in the first string,
// whether continuous or discontinuous
function count_1($a, $b, $m, $n)
{
// If both first and second string is empty,
// or if second string is empty, return 1
if (($m == 0 && $n == 0) || $n == 0)
return 1;
// If only first string is empty and second
// string is not empty, return 0
if ($m == 0)
return 0;
// If last characters are same
// Recur for remaining strings by
// 1. considering last characters of both strings
// 2. ignoring last character of first string
if ($a[$m - 1] == $b[$n - 1])
return count_1($a, $b, $m - 1, $n - 1) +
count_1($a, $b, $m - 1, $n);
else
// If last characters are different, ignore
// last char of first string and recur for
// remaining string
return count_1($a, $b, $m - 1, $n);
}
// Driver code
$a = "GeeksforGeeks";
$b = "Gks";
echo count_1($a, $b, strlen($a), strlen($b)) ."\n";
return 0;
?>
Javascript
<script>
// A Naive recursive javascript program to find the number of
// times the second string occurs in the first string,
// whether continuous or discontinuous
// Recursive function to find the number of times
// the second string occurs in the first string,
// whether continuous or discontinuous
function count( a, b , m , n)
{
// If both first and second string is empty,
// or if second string is empty, return 1
if ((m == 0 && n == 0) || n == 0)
return 1;
// If only first string is empty and
// second string is not empty, return 0
if (m == 0)
return 0;
// If last characters are same
// Recur for remaining strings by
// 1. considering last characters of
// both strings
// 2. ignoring last character of
// first string
if (a[m - 1] == b[n - 1])
return count(a, b, m - 1, n - 1) + count(a, b, m - 1, n);
else
// If last characters are different,
// ignore last char of first string
// and recur for remaining string
return count(a, b, m - 1, n);
}
// Driver code
var a = "GeeksforGeeks";
var b = "Gks";
document.write(count(a, b, a.length, b.length));
// This code is contributed by Amit Katiyar
</script>
4
La complejidad temporal de la solución anterior es exponencial. Si analizamos cuidadosamente, podemos ver que muchos subproblemas se resuelven una y otra vez. Dado que los mismos subproblemas se vuelven a llamar, este problema tiene la propiedad Superposición de subproblemas. Entonces el problema tiene ambas propiedades (ver this y this ) de un problema de programación dinámica. Al igual que otros problemas típicos de programación dinámica, los cálculos de los mismos subproblemas se pueden evitar mediante la construcción de una array temporal que almacene los resultados de los subproblemas.
Podemos resolverlo de 2 maneras.
1) DP de arriba hacia abajo
Podemos extender la solución recursiva y almacenar los estados de dp en un vector 2d para que no volvamos a calcular los subproblemas.
C++
// A Memoization DP C++ program to find the number of
// times the second string occurs in the first string,
// whether continuous or discontinuous
#include <bits/stdc++.h>
using namespace std;
// Memoization DP function to find the number of times
// the second string occurs in the first string,
// whether continuous or discontinuous
int count(string a, string b, int m, int n,
vector<vector<int> >& dp)
{
// If both first and second string is empty,
// or if second string is empty, return 1
if ((m == 0 && n == 0) || n == 0)
return 1;
// If only first string is empty and second
// string is not empty, return 0
if (m == 0)
return 0;
if (dp[m][n] != -1) {
return dp[m][n];
}
// If last characters are same
// Recur for remaining strings by
// 1. considering last characters of both strings
// 2. ignoring last character of first string
if (a[m - 1] == b[n - 1])
return dp[m][n] = count(a, b, m - 1, n - 1, dp)
+ count(a, b, m - 1, n, dp);
else
// If last characters are different, ignore
// last char of first string and recur for
// remaining string
return dp[m][n] = count(a, b, m - 1, n, dp);
}
// Driver code
int main()
{
string a = "GeeksforGeeks";
string b = "Gks";
vector<vector<int> > dp(a.size() + 1,
vector<int>(b.size() + 1, -1));
cout << count(a, b, a.size(), b.size(), dp) << endl;
return 0;
}
4
La complejidad temporal de las soluciones anteriores es O(MN) excluyendo el espacio de la pila de recursividad.
El espacio auxiliar utilizado por el programa es O(MN).
2) PD de abajo hacia arriba
A continuación se muestra su implementación utilizando Programación Dinámica:
C++
// A Dynamic Programming based C++ program to find the
// number of times the second string occurs in the first
// string, whether continuous or discontinuous
#include <iostream>
using namespace std;
// Iterative DP function to find the number of times
// the second string occurs in the first string,
// whether continuous or discontinuous
int count(string a, string b)
{
int m = a.length();
int n = b.length();
// Create a table to store results of sub-problems
int lookup[m + 1][n + 1] = { { 0 } };
// If first string is empty
for (int i = 0; i <= n; ++i)
lookup[0][i] = 0;
// If second string is empty
for (int i = 0; i <= m; ++i)
lookup[i][0] = 1;
// Fill lookup[][] in bottom up manner
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
// If last characters are same, we have two
// options -
// 1. consider last characters of both strings
// in solution
// 2. ignore last character of first string
if (a[i - 1] == b[j - 1])
lookup[i][j] = lookup[i - 1][j - 1] +
lookup[i - 1][j];
else
// If last character are different, ignore
// last character of first string
lookup[i][j] = lookup[i - 1][j];
}
}
return lookup[m][n];
}
// Driver code
int main()
{
string a = "GeeksforGeeks";
string b = "Gks";
cout << count(a, b);
return 0;
}
Java
// A Dynamic Programming based
// Java program to find the
// number of times the second
// string occurs in the first
// string, whether continuous
// or discontinuous
import java.io.*;
class GFG
{
// Iterative DP function to
// find the number of times
// the second string occurs
// in the first string, whether
// continuous or discontinuous
static int count(String a, String b)
{
int m = a.length();
int n = b.length();
// Create a table to store
// results of sub-problems
int lookup[][] = new int[m + 1][n + 1];
// If first string is empty
for (int i = 0; i <= n; ++i)
lookup[0][i] = 0;
// If second string is empty
for (int i = 0; i <= m; ++i)
lookup[i][0] = 1;
// Fill lookup[][] in
// bottom up manner
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
// If last characters are
// same, we have two options -
// 1. consider last characters
// of both strings in solution
// 2. ignore last character
// of first string
if (a.charAt(i - 1) == b.charAt(j - 1))
lookup[i][j] = lookup[i - 1][j - 1] +
lookup[i - 1][j];
else
// If last character are
// different, ignore last
// character of first string
lookup[i][j] = lookup[i - 1][j];
}
}
return lookup[m][n];
}
// Driver Code
public static void main (String[] args)
{
String a = "GeeksforGeeks";
String b = "Gks";
System.out.println(count(a, b));
}
}
// This code is contributed by anuj_67.
Python3
# A Dynamic Programming based Python # program to find the number of times # the second string occurs in the first # string, whether continuous or discontinuous # Iterative DP function to find the # number of times the second string # occurs in the first string, # whether continuous or discontinuous def count(a, b): m = len(a) n = len(b) # Create a table to store results of sub-problems lookup = [[0] * (n + 1) for i in range(m + 1)] # If first string is empty for i in range(n+1): lookup[0][i] = 0 # If second string is empty for i in range(m + 1): lookup[i][0] = 1 # Fill lookup[][] in bottom up manner for i in range(1, m + 1): for j in range(1, n + 1): # If last characters are same, # we have two options - # 1. consider last characters of # both strings in solution # 2. ignore last character of first string if a[i - 1] == b[j - 1]: lookup[i][j] = lookup[i - 1][j - 1] + lookup[i - 1][j] else: # If last character are different, ignore # last character of first string lookup[i][j] = lookup[i - 1][j] return lookup[m][n] # Driver code if __name__ == '__main__': a = "GeeksforGeeks" b = "Gks" print(count(a, b)) # this code is contributed by PranchalK
C#
// A Dynamic Programming based
// C# program to find the
// number of times the second
// string occurs in the first
// string, whether continuous
// or discontinuous
using System;
class GFG
{
// Iterative DP function to
// find the number of times
// the second string occurs
// in the first string, whether
// continuous or discontinuous
static int count(String a, String b)
{
int m = a.Length;
int n = b.Length;
// Create a table to store
// results of sub-problems
int[,] lookup = new int[m + 1, n + 1];
// If first string is empty
for (int i = 0; i <= n; ++i)
lookup[0, i] = 0;
// If second string is empty
for (int i = 0; i <= m; ++i)
lookup[i, 0] = 1;
// Fill lookup[][] in
// bottom up manner
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
// If last characters are
// same, we have two options -
// 1. consider last characters
// of both strings in solution
// 2. ignore last character
// of first string
if (a[i - 1] == b[j - 1])
lookup[i, j] = lookup[i - 1, j - 1] +
lookup[i - 1, j];
else
// If last character are
// different, ignore last
// character of first string
lookup[i, j] = lookup[i - 1, j];
}
}
return lookup[m, n];
}
// Driver Code
public static void Main()
{
String a = "GeeksforGeeks";
String b = "Gks";
Console.WriteLine(count(a, b));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
// A Dynamic Programming based PHP program to find the
// number of times the second string occurs in the first
// string, whether continuous or discontinuous
// Iterative DP function to find the number of times
// the second string occurs in the first string,
// whether continuous or discontinuous
function count1($a, $b)
{
$m = strlen($a);
$n = strlen($b);
// Create a table to store results of sub-problems
$lookup = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
// If second string is empty
for ($i = 0; $i <= $m; ++$i)
$lookup[$i][0] = 1;
// Fill lookup[][] in bottom up manner
for ($i = 1; $i <= $m; $i++)
{
for ($j = 1; $j <= $n; $j++)
{
// If last characters are same, we have two
// options -
// 1. consider last characters of both strings
// in solution
// 2. ignore last character of first string
if ($a[$i - 1] == $b[$j - 1])
$lookup[$i][$j] = $lookup[$i - 1][$j - 1] +
$lookup[$i - 1][$j];
else
// If last character are different, ignore
// last character of first string
$lookup[$i][$j] = $lookup[$i - 1][$j];
}
}
return $lookup[$m][$n];
}
// Driver code
$a = "GeeksforGeeks";
$b = "Gks";
echo count1($a, $b);
// This code is contributed by chandan_jnu
?>
Javascript
<script>
// A Dynamic Programming based
// Javascript program to find the
// number of times the second
// string occurs in the first
// string, whether continuous
// or discontinuous
// Iterative DP function to
// find the number of times
// the second string occurs
// in the first string, whether
// continuous or discontinuous
function count(a, b)
{
var m = a.length;
var n = b.length;
// Create a table to store
// results of sub-problems
var lookup = Array(m + 1);
for(var i = 0; i < m + 1; i++)
lookup[i] = Array(n + 1).fill(0);
// If first string is empty
for(i = 0; i <= n; ++i)
lookup[0][i] = 0;
// If second string is empty
for(i = 0; i <= m; ++i)
lookup[i][0] = 1;
// Fill lookup in
// bottom up manner
for(i = 1; i <= m; i++)
{
for(j = 1; j <= n; j++)
{
// If last characters are
// same, we have two options -
// 1. consider last characters
// of both strings in solution
// 2. ignore last character
// of first string
if (a.charAt(i - 1) == b.charAt(j - 1))
lookup[i][j] = lookup[i - 1][j - 1] +
lookup[i - 1][j];
else
// If last character are
// different, ignore last
// character of first string
lookup[i][j] = lookup[i - 1][j];
}
}
return lookup[m][n];
}
// Driver Code
var a = "GeeksforGeeks";
var b = "Gks";
document.write(count(a, b));
// This code is contributed by gauravrajput1
</script>
4
La complejidad temporal de las soluciones anteriores es O(MN).
El espacio auxiliar utilizado por el programa es O(MN).
Otro método :
Este método fue aportado por Kunal Hotwani
Podemos resolver este problema considerando el hecho de que, en las subsecuencias finales que se elegirán en la cuenta, el carácter en b[i] siempre seguirá al carácter en b[i – 1] (por la definición de una subsecuencia) .
Usando este hecho, contamos el número total de ocurrencias de la string b , usando una array de tamaño igual a la longitud de la string b .
Podemos crear una array de tamaño igual a n (b.size()), el j -ésimo elemento en esta array almacena el número de subsecuencias en la string a que son iguales a b[0]b[1]…b[j ] . Atravesaremos la string a , cada vez que actualicemos todos los valores en esta array. Llamemos a esta array conteo.
Mientras recorremos la string a , recorreremos la string b en sentido inverso para cada carácter de a, digamos que estamos en el i -ésimo carácter de a (a[i]) y comenzamos el recorrido inverso de b, si el j -ésimo carácter de b (b[j]) es igual a a[i], a[i] se le puede agregar a todas las subsecuencias de a (recorridas hasta ahora) que son iguales a b[0]b[1]… b[j – 1] (el número de este tipo de subsecuencias se almacena en count[j -1]), lo que hace que las subsecuencias sean iguales a b[0]b[1]…b[j](el número de este tipo de subsecuencias se almacena en count[j]), por lo tanto, count[j] puede incrementarse en count[j – 1], cuando encontramos un carácter en la string b que es igual a a[i].
NOTA: Cuando j es igual a 0, el carácter a[i] no se puede agregar a ninguna subsecuencia, sino que puede comenzar una nueva subsecuencia igual a b[0] , por lo tanto, cuando a[i] es igual a b[0], aumentamos count[0] en 1 (ya que almacena el recuento de todas las subsecuencias de tipo b[0] ).
Así, en este método estamos contando todas las subsecuencias de un tipo b[0]b[1]…b[j] que pueden crearse usando un carácter particular de a ,a[i].
Finalmente, después de recorrer la string completa a, la respuesta final se almacenará en count[n – 1], ya que requerimos el número de subsecuencias de tipo b[0]b[1]…b[n – 1] .
La razón del recorrido de b en reversa
Consideremos b = geeks, crearemos la array de conteo de tamaño 5 y comenzaremos el recorrido de la string b desde el frente para cada a[i].
Cuando a[i] = ‘e’, primero aumentaremos count[1] (que representa la primera e en la string b ) en count[0], y luego aumentaremos count[2] (que representa la segunda e en la string b ) en count[1], esto no es ideal porque siempre necesitamos el valor de count[j – 1] para representar el número de subsecuencias de tipo b[0]b[1]…b[j – 1] en la string a[ 0]a[1]…a[i – 1] ya que no podemos usar la misma ‘e’ dos veces en una subsecuencia (En este caso, count[1] representará a[i] agregado a todas las subsecuencias de tipo b[0 ] y usando este conteo[1] para actualizar el conteo[2], lo que significa que usamos la misma ‘e’ dos veces).
A continuación se muestra el código para este enfoque.
C++
#include <bits/stdc++.h>
using namespace std;
int countWays(string S1, string S2)
{
int m = S1.size(), n = S2.size();
vector<int> count(n, 0);
// Initialization to 0 is done because if a is not traversed yet,
// no subsequence of any type b[0]b[1]...b[i] can exist, i.e. the
// number is zero.
for (int i = 0; i < m; i++) // Traversing the string a
{
for (int j = n - 1; j >= 0; j--) // Reverse traversal of b
{
if (S1[i] == S2[j])
{
// This ternary expression checks weather j == 0,
// gives 1 if j == 0.
count[j] += (j == 0 ? 1 : count[j - 1]);
}
}
}
return count[n - 1];
}
int main()
{
string S1 = "geeksforgeeks", S2 = "geeks";
cout << countWays(S1, S2) << "\n";
return 0;
}
9
La complejidad temporal de las soluciones anteriores es O(MN).
El espacio auxiliar utilizado por el programa es O(N).
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.GeeksforGeeks.org o envíe su artículo por correo a contribuya@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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA