Dadas dos strings A y B . La tarea es contar el número de formas de insertar un carácter en la string A para aumentar la longitud de la subsecuencia común más larga entre la string A y la string B en 1.
Ejemplos:
Entrada: A = “aa”, B = “baaa”
Salida: 4
La subsecuencia común más larga compartida por la string A y la string B es “aa”, que tiene una longitud de 2.
Hay dos formas en que la longitud del común más largo La subsecuencia se puede aumentar a 3 agregando un solo carácter a la string A:
- Hay 3 posiciones diferentes en la string A donde podríamos insertar una ‘a’ adicional para crear la subsecuencia común más larga “aaa” (es decir, al principio, en el medio y al final de la string).
- Podemos insertar una ‘b’ al comienzo de la string para una nueva subsecuencia común más larga de “baaa”. Entonces, tenemos 3 + 1 = 4 formas de insertar un carácter alfanumérico en la string A y aumentar la longitud de la subsecuencia común más larga en uno.
Digamos que para una string A y una string B dadas, la longitud de su LCS es k . Insertemos un solo carácter ‘c’ después del i-ésimo carácter en la string A y denotemos la string formada después de la inserción como string A new , que se parece a:
A new = A 1, i . C . A yo + 1, norte
donde A i, j denota una substring de la string A del i-ésimo al j-ésimo carácter y ‘.’ denota una concatenación de dos strings.
Definamos k new como la longitud del LCS de A new y B. Ahora queremos saber si k new = k + 1.
La observación crucial es que el carácter ‘c’ recién insertado debe ser parte de cualquier subsecuencia común de A new y B que tenga una longitud > k. Sabemos esto porque si hay alguna subsecuencia común de A new y B, esto es una contradicción porque significaría que la longitud de la LCS de A y B es > k.
Usando la observación anterior, podemos probar el siguiente enfoque. Para cada posible carácter ‘c’ (hay 52 letras mayúsculas y minúsculas en inglés y 10 dígitos arábigos, por lo que hay 62 caracteres posibles para insertar) y para cada posible inserción i en la String A (hay |a| + 1 posiciones de inserción ), intentemos insertar ‘c’ después del i-ésimo carácter en la string A y hacerlo coincidir con cada aparición de ‘c’ en la string B, podemos intentar hacer coincidir estos caracteres ‘c’ de manera que:
A 1, i . C . Ai +1, nB1
, j-1 . C . Bj +1, m
Ahora, para verificar si tal inserción produce un LCS de longitud k + 1, es suficiente verificar si la longitud del LCS de A 1, i y B 1, j-1 más la longitud del LCS A i+ 1, n y B j+1, m es igual a k. En este caso, el lCS de A nuevo y B es k + 1 porque hay una coincidencia entre las ocurrencias fijas del carácter ‘c’ y ya no hay una subsecuencia común entre ellos.
Si podemos obtener rápidamente la longitud del LCS entre cada dos prefijos de A y B, así como entre cada dos de sus sufijos, podemos calcular el resultado. La longitud del LCS entre sus prefijos se puede leer en una tabla de programación dinámica utilizada para calcular el LCS de la string A y la string B. En este método, dp[i][j] almacena la longitud de la subsecuencia común más larga de A , i y B i, j . De manera similar, la longitud del LCS entre sus sufijos se puede leer en una tabla dp análoga que se puede calcular durante el cálculo del LCS de A invertido y B invertido donde S invertido denota la string S invertida.
Implementación:
C++
// CPP Program to Number of ways to insert a
// character to increase LCS by one
#include <bits/stdc++.h>
#define MAX 256
using namespace std;
// Return the Number of ways to insert a
// character to increase the Longest
// Common Subsequence by one
int numberofways(string A, string B, int N, int M)
{
vector<int> pos[MAX];
// Insert all positions of all characters
// in string B.
for (int i = 0; i < M; i++)
pos[B[i]].push_back(i + 1);
// Longest Common Subsequence
int dpl[N + 2][M + 2];
memset(dpl, 0, sizeof(dpl));
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (A[i - 1] == B[j - 1])
dpl[i][j] = dpl[i - 1][j - 1] + 1;
else
dpl[i][j] = max(dpl[i - 1][j],
dpl[i][j - 1]);
}
}
int LCS = dpl[N][M];
// Longest Common Subsequence from reverse
int dpr[N + 2][M + 2];
memset(dpr, 0, sizeof(dpr));
for (int i = N; i >= 1; i--) {
for (int j = M; j >= 1; j--) {
if (A[i - 1] == B[j - 1])
dpr[i][j] = dpr[i + 1][j + 1] + 1;
else
dpr[i][j] = max(dpr[i + 1][j],
dpr[i][j + 1]);
}
}
// inserting character between position
// i and i+1
int ans = 0;
for (int i = 0; i <= N; i++) {
for (int j = 0; j < MAX; j++) {
for (auto x : pos[j]) {
if (dpl[i][x - 1] + dpr[i + 1][x + 1] == LCS) {
ans++;
break;
}
}
}
}
return ans;
}
// Driver Program
int main()
{
string A = "aa", B = "baaa";
int N = A.length(), M = B.length();
cout << numberofways(A, B, N, M) << endl;
return 0;
}
Java
// Java Program for Number of ways to insert a
// character to increase LCS by one
import java.util.*;
class GFG
{
static final int MAX = 256;
// Return the Number of ways to insert a
// character to increase the Longest
// Common Subsequence by one
static int numberofways(String A, String B, int N, int M)
{
Vector<Integer>[] pos = new Vector[MAX];
// Insert all positions of all characters
// in string B.
for (int i = 0; i < MAX; i++)
pos[i] = new Vector<>();
for (int i = 0; i < M; i++)
pos[B.charAt(i)].add(i + 1);
// Longest Common Subsequence
int[][] dpl = new int[N + 2][M + 2];
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
if (A.charAt(i - 1) == B.charAt(j - 1))
dpl[i][j] = dpl[i - 1][j - 1] + 1;
else
dpl[i][j] = Math.max(dpl[i - 1][j],
dpl[i][j - 1]);
}
}
int LCS = dpl[N][M];
// Longest Common Subsequence from reverse
int[][] dpr = new int[N + 2][M + 2];
for (int i = N; i >= 1; i--)
{
for (int j = M; j >= 1; j--)
{
if (A.charAt(i - 1) == B.charAt(j - 1))
dpr[i][j] = dpr[i + 1][j + 1] + 1;
else
dpr[i][j] = Math.max(dpr[i + 1][j],
dpr[i][j + 1]);
}
}
// inserting character between position
// i and i+1
int ans = 0;
for (int i = 0; i <= N; i++)
{
for (int j = 0; j < MAX; j++)
{
for (int x : pos[j])
{
if (dpl[i][x - 1] +
dpr[i + 1][x + 1] == LCS)
{
ans++;
break;
}
}
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
String A = "aa", B = "baaa";
int N = A.length(), M = B.length();
System.out.println(numberofways(A, B, N, M));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python Program to Number of ways to insert a # character to increase LCS by one MAX = 256 def numberofways(A, B, N, M): pos = [[] for _ in range(MAX)] # Insert all positions of all characters # in string B for i in range(M): pos[ord(B[i])].append(i+1) # Longest Common Subsequence dpl = [[0] * (M+2) for _ in range(N+2)] for i in range(1, N+1): for j in range(1, M+1): if A[i - 1] == B[j - 1]: dpl[i][j] = dpl[i - 1][j - 1] + 1 else: dpl[i][j] = max(dpl[i - 1][j], dpl[i][j - 1]) LCS = dpl[N][M] # Longest Common Subsequence from reverse dpr = [[0] * (M+2) for _ in range(N+2)] for i in range(N, 0, -1): for j in range(M, 0, -1): if A[i - 1] == B[j - 1]: dpr[i][j] = dpr[i + 1][j + 1] + 1 else: dpr[i][j] = max(dpr[i + 1][j], dpr[i][j + 1]) # inserting character between position # i and i+1 ans = 0 for i in range(N+1): for j in range(MAX): for x in pos[j]: if dpl[i][x - 1] + dpr[i + 1][x + 1] == LCS: ans += 1 break return ans # Driver Code if __name__ == "__main__": A = "aa" B = "baaa" N = len(A) M = len(B) print(numberofways(A, B, N, M)) # This code is contributed by vibhu4agarwal
C#
// C# Program for Number of ways to insert a
// character to increase LCS by one
using System;
using System.Collections.Generic;
class GFG
{
static readonly int MAX = 256;
// Return the Number of ways to insert a
// character to increase the longest
// Common Subsequence by one
static int numberofways(String A, String B,
int N, int M)
{
List<int>[] pos = new List<int>[MAX];
// Insert all positions of all characters
// in string B.
for (int i = 0; i < MAX; i++)
pos[i] = new List<int>();
for (int i = 0; i < M; i++)
pos[B[i]].Add(i + 1);
// longest Common Subsequence
int[,] dpl = new int[N + 2, M + 2];
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
if (A[i - 1] == B[j - 1])
dpl[i, j] = dpl[i - 1, j - 1] + 1;
else
dpl[i, j] = Math.Max(dpl[i - 1, j],
dpl[i, j - 1]);
}
}
int LCS = dpl[N, M];
// longest Common Subsequence from reverse
int[,] dpr = new int[N + 2, M + 2];
for (int i = N; i >= 1; i--)
{
for (int j = M; j >= 1; j--)
{
if (A[i - 1] == B[j - 1])
dpr[i, j] = dpr[i + 1, j + 1] + 1;
else
dpr[i, j] = Math.Max(dpr[i + 1, j],
dpr[i, j + 1]);
}
}
// inserting character between position
// i and i+1
int ans = 0;
for (int i = 0; i <= N; i++)
{
for (int j = 0; j < MAX; j++)
{
foreach (int x in pos[j])
{
if (dpl[i, x - 1] +
dpr[i + 1, x + 1] == LCS)
{
ans++;
break;
}
}
}
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
String A = "aa", B = "baaa";
int N = A.Length, M = B.Length;
Console.WriteLine(numberofways(A, B, N, M));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript Program for Number of ways to insert a
// character to increase LCS by one
let MAX = 256;
// Return the Number of ways to insert a
// character to increase the Longest
// Common Subsequence by one
function numberofways(A,B,N,M)
{
let pos = new Array(MAX);
// Insert all positions of all characters
// in string B.
for (let i = 0; i < MAX; i++)
pos[i] =[];
for (let i = 0; i < M; i++)
pos[B[i].charCodeAt(0)].push(i + 1);
// Longest Common Subsequence
let dpl = new Array(N + 2);
for(let i=0;i<N+2;i++)
{
dpl[i]=new Array(M+2);
for(let j=0;j<M+2;j++)
dpl[i][j]=0;
}
for (let i = 1; i <= N; i++)
{
for (let j = 1; j <= M; j++)
{
if (A[i - 1] == B[j - 1])
dpl[i][j] = dpl[i - 1][j - 1] + 1;
else
dpl[i][j] = Math.max(dpl[i - 1][j],
dpl[i][j - 1]);
}
}
let LCS = dpl[N][M];
// Longest Common Subsequence from reverse
let dpr = new Array(N + 2);
for(let i=0;i<N+2;i++)
{
dpr[i]=new Array(M+2);
for(let j=0;j<M+2;j++)
dpr[i][j]=0;
}
for (let i = N; i >= 1; i--)
{
for (let j = M; j >= 1; j--)
{
if (A[i - 1] == B[j - 1])
dpr[i][j] = dpr[i + 1][j + 1] + 1;
else
dpr[i][j] = Math.max(dpr[i + 1][j],
dpr[i][j + 1]);
}
}
// inserting character between position
// i and i+1
let ans = 0;
for (let i = 0; i <= N; i++)
{
for (let j = 0; j < MAX; j++)
{
for (let x=0;x< pos[j].length;x++)
{
if (dpl[i][pos[j][x] - 1] +
dpr[i + 1][pos[j][x] + 1] == LCS)
{
ans++;
break;
}
}
}
}
return ans;
}
// Driver Code
let A = "aa", B = "baaa";
let N = A.length, M = B.length;
document.write(numberofways(A, B, N, M));
// This code is contributed by rag2127
</script>
4
Complejidad temporal: O(N x M)