Dadas dos strings de caracteres del alfabeto inferior, necesitamos encontrar el número de formas de insertar un carácter en la primera string de modo que la longitud de LCS de ambas strings aumente en uno.
Ejemplos:
Input : str1 = “abab”, str2 = “abc” Output : 3 LCS length of given two strings is 2. There are 3 ways of insertion in str1, to increase the LCS length by one which are enumerated below, str1 = “abcab” str2 = “abc” LCS length = 3 str1 = “abacb” str2 = “abc” LCS length = 3 str1 = “ababc” str2 = “abc” LCS length = 3 Input : str1 = “abcabc”, str2 = “abcd” Output : 4
La idea es probar los 26 caracteres posibles en cada posición de la primera string, si la longitud de str1 es m, entonces se puede insertar un nuevo carácter en (m + 1) posiciones, ahora suponga que en cualquier momento se inserta el carácter c en la i-ésima posición en str1 luego lo emparejaremos con todas las posiciones que tengan el carácter c en str2. Supongamos que una de esas posiciones es j, entonces para que la longitud total de LCS sea una más que la anterior, la siguiente condición debe cumplir,
LCS(str1[1, m], str2[1, n]) = LCS(str1[1, i], str2[1, j-1]) +
LCS(str1[i+1, m], str2[j+1, n])
La ecuación anterior establece que la suma de LCS de las substrings de sufijo y prefijo en el carácter insertado debe ser la misma que la LCS total de las strings, de modo que cuando se inserta el mismo carácter en la primera string, aumentará la longitud de LCS en uno.
En el siguiente código, se utilizan dos arrays 2D, lcsl y lcsr para almacenar LCS de prefijo y sufijo de strings, respectivamente. El método para llenar estas arrays 2D se puede encontrar aquí .
Consulte el código a continuación para una mejor comprensión,
C++
// C++ program to get number of ways to increase
// LCS by 1
#include <bits/stdc++.h>
using namespace std;
#define M 26
// Utility method to get integer position of lower
// alphabet character
int toInt(char ch)
{
return (ch - 'a');
}
// Method returns total ways to increase LCS length by 1
int waysToIncreaseLCSBy1(string str1, string str2)
{
int m = str1.length(), n = str2.length();
// Fill positions of each character in vector
vector<int> position[M];
for (int i = 1; i <= n; i++)
position[toInt(str2[i-1])].push_back(i);
int lcsl[m + 2][n + 2];
int lcsr[m + 2][n + 2];
// Initializing 2D array by 0 values
for (int i = 0; i <= m+1; i++)
for (int j = 0; j <= n + 1; j++)
lcsl[i][j] = lcsr[i][j] = 0;
// Filling LCS array for prefix substrings
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if (str1[i-1] == str2[j-1])
lcsl[i][j] = 1 + lcsl[i-1][j-1];
else
lcsl[i][j] = max(lcsl[i-1][j],
lcsl[i][j-1]);
}
}
// Filling LCS array for suffix substrings
for (int i = m; i >= 1; i--)
{
for (int j = n; j >= 1; j--)
{
if (str1[i-1] == str2[j-1])
lcsr[i][j] = 1 + lcsr[i+1][j+1];
else
lcsr[i][j] = max(lcsr[i+1][j],
lcsr[i][j+1]);
}
}
// Looping for all possible insertion positions
// in first string
int ways = 0;
for (int i=0; i<=m; i++)
{
// Trying all possible lower case characters
for (char c='a'; c<='z'; c++)
{
// Now for each character, loop over same
// character positions in second string
for (int j=0; j<position[toInt(c)].size(); j++)
{
int p = position[toInt(c)][j];
// If both, left and right substrings make
// total LCS then increase result by 1
if (lcsl[i][p-1] + lcsr[i+1][p+1] == lcsl[m][n])
ways++;
}
}
}
return ways;
}
// Driver code to test above methods
int main()
{
string str1 = "abcabc";
string str2 = "abcd";
cout << waysToIncreaseLCSBy1(str1, str2);
return 0;
}
Java
// Java program to get number of ways to increase
// LCS by 1
import java.util.*;
class GFG
{
static int M = 26;
// Method returns total ways to increase
// LCS length by 1
static int waysToIncreaseLCSBy1(String str1,
String str2)
{
int m = str1.length(), n = str2.length();
// Fill positions of each character in vector
Vector<Integer>[] position = new Vector[M];
for (int i = 0; i < M; i++)
position[i] = new Vector<>();
for (int i = 1; i <= n; i++)
position[str2.charAt(i - 1) - 'a'].add(i);
int[][] lcsl = new int[m + 2][n + 2];
int[][] lcsr = new int[m + 2][n + 2];
// Initializing 2D array by 0 values
for (int i = 0; i <= m + 1; i++)
for (int j = 0; j <= n + 1; j++)
lcsl[i][j] = lcsr[i][j] = 0;
// Filling LCS array for prefix substrings
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if (str1.charAt(i - 1) == str2.charAt(j - 1))
lcsl[i][j] = 1 + lcsl[i - 1][j - 1];
else
lcsl[i][j] = Math.max(lcsl[i - 1][j],
lcsl[i][j - 1]);
}
}
// Filling LCS array for suffix substrings
for (int i = m; i >= 1; i--)
{
for (int j = n; j >= 1; j--)
{
if (str1.charAt(i - 1) == str2.charAt(j - 1))
lcsr[i][j] = 1 + lcsr[i + 1][j + 1];
else
lcsr[i][j] = Math.max(lcsr[i + 1][j],
lcsr[i][j + 1]);
}
}
// Looping for all possible insertion positions
// in first string
int ways = 0;
for (int i = 0; i <= m; i++)
{
// Trying all possible lower case characters
for (char d = 0; d < 26; d++)
{
// Now for each character, loop over same
// character positions in second string
for (int j = 0; j < position[d].size(); j++)
{
int p = position[d].elementAt(j);
// If both, left and right substrings make
// total LCS then increase result by 1
if (lcsl[i][p - 1] +
lcsr[i + 1][p + 1] == lcsl[m][n])
ways++;
}
}
}
return ways;
}
// Driver Code
public static void main(String[] args)
{
String str1 = "abcabc";
String str2 = "abcd";
System.out.println(waysToIncreaseLCSBy1(str1, str2));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to get number of ways to increase # LCS by 1 M = 26 # Method returns total ways to increase LCS length by 1 def waysToIncreaseLCSBy1(str1, str2): m = len(str1) n = len(str2) # Fill positions of each character in vector # vector<int> position[M]; position = [[] for i in range(M)] for i in range(1, n+1, 1): position[ord(str2[i-1])-97].append(i) # Initializing 2D array by 0 values lcsl = [[0 for i in range(n+2)] for j in range(m+2)] lcsr = [[0 for i in range(n+2)] for j in range(m+2)] # Filling LCS array for prefix substrings for i in range(1, m+1, 1): for j in range(1, n+1,1): if (str1[i-1] == str2[j-1]): lcsl[i][j] = 1 + lcsl[i-1][j-1] else: lcsl[i][j] = max(lcsl[i-1][j], lcsl[i][j-1]) # Filling LCS array for suffix substrings for i in range(m, 0, -1): for j in range(n, 0, -1): if (str1[i-1] == str2[j-1]): lcsr[i][j] = 1 + lcsr[i+1][j+1] else: lcsr[i][j] = max(lcsr[i+1][j], lcsr[i][j+1]) # Looping for all possible insertion positions # in first string ways = 0 for i in range(0, m+1,1): # Trying all possible lower case characters for C in range(0, 26,1): # Now for each character, loop over same # character positions in second string for j in range(0, len(position[C]),1): p = position[C][j] # If both, left and right substrings make # total LCS then increase result by 1 if (lcsl[i][p-1] + lcsr[i+1][p+1] == lcsl[m][n]): ways += 1 return ways # Driver code to test above methods str1 = "abcabc" str2 = "abcd" print(waysToIncreaseLCSBy1(str1, str2)) # This code is contributed by ankush_953
C#
// C# program to get number of ways
// to increase LCS by 1
using System;
using System.Collections.Generic;
class GFG{
static int M = 26;
// Method returns total ways to increase
// LCS length by 1
static int waysToIncreaseLCSBy1(String str1,
String str2)
{
int m = str1.Length, n = str2.Length;
// Fill positions of each character in vector
List<int>[] position = new List<int>[M];
for(int i = 0; i < M; i++)
position[i] = new List<int>();
for(int i = 1; i <= n; i++)
position[str2[i - 1] - 'a'].Add(i);
int[,] lcsl = new int[m + 2, n + 2];
int[,] lcsr = new int[m + 2, n + 2];
// Initializing 2D array by 0 values
for(int i = 0; i <= m + 1; i++)
for(int j = 0; j <= n + 1; j++)
lcsl[i, j] = lcsr[i, j] = 0;
// Filling LCS array for prefix substrings
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
if (str1[i - 1] == str2[j - 1])
lcsl[i, j] = 1 + lcsl[i - 1, j - 1];
else
lcsl[i, j] = Math.Max(lcsl[i - 1, j],
lcsl[i, j - 1]);
}
}
// Filling LCS array for suffix substrings
for(int i = m; i >= 1; i--)
{
for(int j = n; j >= 1; j--)
{
if (str1[i - 1] == str2[j - 1])
lcsr[i, j] = 1 + lcsr[i + 1, j + 1];
else
lcsr[i, j] = Math.Max(lcsr[i + 1, j],
lcsr[i, j + 1]);
}
}
// Looping for all possible insertion
// positions in first string
int ways = 0;
for(int i = 0; i <= m; i++)
{
// Trying all possible lower
// case characters
for(int d = 0; d < 26; d++)
{
// Now for each character, loop over same
// character positions in second string
for(int j = 0; j < position[d].Count; j++)
{
int p = position[d][j];
// If both, left and right substrings make
// total LCS then increase result by 1
if (lcsl[i, p - 1] +
lcsr[i + 1, p + 1] == lcsl[m, n])
ways++;
}
}
}
return ways;
}
// Driver Code
public static void Main(String[] args)
{
String str1 = "abcabc";
String str2 = "abcd";
Console.WriteLine(waysToIncreaseLCSBy1(str1, str2));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program to get number of ways to increase
// LCS by 1
let M = 26
// Method returns total ways to increase LCS length by 1
function waysToIncreaseLCSBy1(str1, str2)
{
let m = str1.length;
let n = str2.length;
// Fill positions of each character in vector
// vector<int> position[M];
let position = new Array(M);
for(let i = 0; i < M; i++)
position[i] = [];
for(let i = 1; i < n + 1; i++)
{
position[str2.charCodeAt(i-1)-97].push(i)
}
// Initializing 2D array by 0 values
let lcsl = new Array(m+2);
for(let i = 0; i < m + 2; i++)
{
lcsl[i] = new Array(n+2).fill(0);
}
let lcsr = new Array(m + 2);
for(let i = 0; i < m + 2; i++)
{
lcsr[i] = new Array(n+2).fill(0);
}
// Filling LCS array for prefix substrings
for(let i = 1; i < m + 1; i++)
{
for(let j = 1; j < n + 1; j++)
{
if (str1[i-1] == str2[j-1])
lcsl[i][j] = 1 + lcsl[i-1][j-1]
else
lcsl[i][j] = Math.max(lcsl[i-1][j],
lcsl[i][j-1])
}
}
// Filling LCS array for suffix substrings
for(let i = m; i > 0; i--)
{
for(let j = n; j > 0; j--)
{
if (str1[i-1] == str2[j-1])
lcsr[i][j] = 1 + lcsr[i+1][j+1]
else
lcsr[i][j] = Math.max(lcsr[i+1][j],
lcsr[i][j+1])
}
}
// Looping for all possible insertion positions
// in first string
let ways = 0
for(let i = 0; i < m + 1; i++)
{
// Trying all possible lower case characters
for(let C = 0; C < 26; C++)
{
// Now for each character, loop over same
// character positions in second string
for(let j = 0; j < position[C].length; j++)
{
let p = position[C][j]
// If both, left and right substrings make
// total LCS then increase result by 1
if (lcsl[i][p-1] + lcsr[i+1][p+1] == lcsl[m][n])
ways += 1
}
}
}
return ways
}
// Driver code to test above methods
let str1 = "abcabc"
let str2 = "abcd"
document.write(waysToIncreaseLCSBy1(str1, str2))
// This code is contributed by shinjanpatra
</script>
Producción
4
Complejidad de Tiempo : O(mn)
Espacio Auxiliar : O(mn)
Este artículo es una contribución de Utkarsh Trivedi . 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.
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