Dadas dos strings S y Q . La tarea es contar el número de la subsecuencia común en S y T.
Ejemplos:
Entrada: S = “ajblqcpdz”, T = “aefcnbtdi”
Salida: 11
Las subsecuencias comunes son: { “a”, “b”, “c”, “d”, “ab”, “bd”, “ad”, “ ac”, “cd”, “abd”, “acd” }Entrada: S = “a”, T = “ab”
Salida: 1
Para encontrar el número de subsecuencias comunes en dos strings, digamos S y T, usamos Programación Dinámica definiendo una array 2D dp[][] , donde dp[i][j] es el número de subsecuencias comunes en la string S[ 0…i-1] y T[0….j-1].
Ahora, podemos definir dp[i][j] como
= dp[i][j-1] + dp[i-1][j] + 1, cuando S[i-1] es igual a T[j- 1]
Esto se debe a que cuando S[i-1] == S[j-1], utilizando el hecho anterior, todas las subsecuencias comunes anteriores se duplican a medida que se les agrega un carácter más. Tanto dp[i][j-1] como dp[i-1][j] contienen dp[i-1][j-1] y, por lo tanto, se agrega dos veces en nuestra recurrencia que se encarga de duplicar la cuenta de todas las subsecuencias comunes anteriores. La adición de 1 en la recurrencia es para la última coincidencia de caracteres: subsecuencia común compuesta por s1[i-1] y s2[j-1]
= dp[i-1][j] + dp[i][j-1] – dp[i-1][j-1], cuando S[i-1] no es igual a T[j-1]
Aquí restamos dp[i-1][j-1] una vez porque está presente tanto en dp[i][j – 1] como en dp[i – 1][j] y se suma dos veces.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to count common subsequence in two strings
#include <bits/stdc++.h>
using namespace std;
// return the number of common subsequence in
// two strings
int CommomSubsequencesCount(string s, string t)
{
int n1 = s.length();
int n2 = t.length();
int dp[n1+1][n2+1];
for (int i = 0; i <= n1; i++) {
for (int j = 0; j <= n2; j++) {
dp[i][j] = 0;
}
}
// for each character of S
for (int i = 1; i <= n1; i++) {
// for each character in T
for (int j = 1; j <= n2; j++) {
// if character are same in both
// the string
if (s[i - 1] == t[j - 1])
dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
else
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] -
dp[i - 1][j - 1];
}
}
return dp[n1][n2];
}
// Driver Program
int main()
{
string s = "ajblqcpdz";
string t = "aefcnbtdi";
cout << CommomSubsequencesCount(s, t) << endl;
return 0;
}
Java
// Java program to count common subsequence in two strings
public class GFG {
// return the number of common subsequence in
// two strings
static int CommomSubsequencesCount(String s, String t)
{
int n1 = s.length();
int n2 = t.length();
int dp[][] = new int [n1+1][n2+1];
char ch1,ch2 ;
for (int i = 0; i <= n1; i++) {
for (int j = 0; j <= n2; j++) {
dp[i][j] = 0;
}
}
// for each character of S
for (int i = 1; i <= n1; i++) {
// for each character in T
for (int j = 1; j <= n2; j++) {
ch1 = s.charAt(i - 1);
ch2 = t.charAt(j - 1);
// if character are same in both
// the string
if (ch1 == ch2)
dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
else
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] -
dp[i - 1][j - 1];
}
}
return dp[n1][n2];
}
// Driver code
public static void main (String args[]){
String s = "ajblqcpdz";
String t = "aefcnbtdi";
System.out.println(CommomSubsequencesCount(s, t));
}
// This code is contributed by ANKITRAI1
}
Python3
# Python3 program to count common # subsequence in two strings # return the number of common subsequence # in two strings def CommomSubsequencesCount(s, t): n1 = len(s) n2 = len(t) dp = [[0 for i in range(n2 + 1)] for i in range(n1 + 1)] # for each character of S for i in range(1, n1 + 1): # for each character in T for j in range(1, n2 + 1): # if character are same in both # the string if (s[i - 1] == t[j - 1]): dp[i][j] = (1 + dp[i][j - 1] + dp[i - 1][j]) else: dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]) return dp[n1][n2] # Driver Code s = "ajblqcpdz" t = "aefcnbtdi" print(CommomSubsequencesCount(s, t)) # This code is contributed by Mohit Kumar
C#
// C# program to count common
// subsequence in two strings
using System;
class GFG
{
// return the number of common
// subsequence in two strings
static int CommomSubsequencesCount(string s,
string t)
{
int n1 = s.Length;
int n2 = t.Length;
int[,] dp = new int [n1 + 1, n2 + 1];
for (int i = 0; i <= n1; i++)
{
for (int j = 0; j <= n2; j++)
{
dp[i, j] = 0;
}
}
// for each character of S
for (int i = 1; i <= n1; i++)
{
// for each character in T
for (int j = 1; j <= n2; j++)
{
// if character are same in
// both the string
if (s[i - 1] == t[j - 1])
dp[i, j] = 1 + dp[i, j - 1] +
dp[i - 1, j];
else
dp[i, j] = dp[i, j - 1] +
dp[i - 1, j] -
dp[i - 1, j - 1];
}
}
return dp[n1, n2];
}
// Driver code
public static void Main ()
{
string s = "ajblqcpdz";
string t = "aefcnbtdi";
Console.Write(CommomSubsequencesCount(s, t));
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP program to count common subsequence
// in two strings
// return the number of common subsequence
// in two strings
function CommomSubsequencesCount($s, $t)
{
$n1 = strlen($s);
$n2 = strlen($t);
$dp = array();
for ($i = 0; $i <= $n1; $i++)
{
for ($j = 0; $j <= $n2; $j++)
{
$dp[$i][$j] = 0;
}
}
// for each character of S
for ($i = 1; $i <= $n1; $i++)
{
// for each character in T
for ($j = 1; $j <= $n2; $j++)
{
// if character are same in both
// the string
if ($s[$i - 1] == $t[$j - 1])
$dp[$i][$j] = 1 + $dp[$i][$j - 1] +
$dp[$i - 1][$j];
else
$dp[$i][$j] = $dp[$i][$j - 1] +
$dp[$i - 1][$j] -
$dp[$i - 1][$j - 1];
}
}
return $dp[$n1][$n2];
}
// Driver Code
$s = "ajblqcpdz";
$t = "aefcnbtdi";
echo CommomSubsequencesCount($s, $t) ."\n";
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript program to count common subsequence in two strings
// return the number of common subsequence in
// two strings
function CommomSubsequencesCount(s, t)
{
var n1 = s.length;
var n2 = t.length;
var dp = Array.from(Array(n1+1), ()=> Array(n2+1));
for (var i = 0; i <= n1; i++) {
for (var j = 0; j <= n2; j++) {
dp[i][j] = 0;
}
}
// for each character of S
for (var i = 1; i <= n1; i++) {
// for each character in T
for (var j = 1; j <= n2; j++) {
// if character are same in both
// the string
if (s[i - 1] == t[j - 1])
dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j];
else
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] -
dp[i - 1][j - 1];
}
}
return dp[n1][n2];
}
// Driver Program
var s = "ajblqcpdz";
var t = "aefcnbtdi";
document.write( CommomSubsequencesCount(s, t));
</script>
11
Complejidad de tiempo: O (n1 * n2)
Espacio auxiliar: O (n1 * n2)
Fuente: StackOverflow