Longest Common Substring (solução de DP otimizada para espaço)
Dadas duas strings 'X' e 'Y', encontre o comprimento da substring comum mais longa. A complexidade espacial esperada é linear.
Exemplos :
Input : X = "GeeksforGeeks", Y = "GeeksQuiz" Output : 5 The longest common substring is "Geeks" and is of length 5. Input : X = "abcdxyz", Y = "xyzabcd" Output : 4 The longest common substring is "abcd" and is of length 4.
Discutimos a solução baseada em programação dinâmica para a substring comum mais longa. O espaço auxiliar usado pela solução é O (m * n), onde m e n são os comprimentos das cadeias X e Y. O espaço usado pela solução pode ser reduzido a O (2 * n).
Suponha que estejamos na posição mat [i] [j]. Agora, se X [i-1] == Y [j-1], então adicionamos o valor de mat [i-1] [j-1] ao nosso resultado. Ou seja, adicionamos valor da linha anterior e o valor de todas as outras linhas abaixo da linha anterior nunca é usado. Portanto, por vez, estamos usando apenas duas linhas consecutivas. Essa observação pode ser usada para reduzir o espaço necessário para encontrar o comprimento da substring comum mais longa.
Em vez de criar uma array de tamanho m * n, criamos uma array de tamanho 2 * n. Uma variável currRow é usada para representar que a linha 0 ou a linha 1 desta array é usada atualmente para encontrar o comprimento. Inicialmente, a linha 0 é usada como linha atual para o caso em que o comprimento da string X é zero. No final de cada iteração, a linha atual é transformada em linha anterior e a linha anterior é transformada em nova linha atual.
// Space optimized CPP implementation of longest
// common substring.
#include <bits/stdc++.h>
using namespace std;
// Function to find longest common substring.
int LCSubStr(string X, string Y)
{
// Find length of both the strings.
int m = X.length();
int n = Y.length();
// Variable to store length of longest
// common substring.
int result = 0;
// Matrix to store result of two
// consecutive rows at a time.
int len[2][n];
// Variable to represent which row of
// matrix is current row.
int currRow = 0;
// For a particular value of i and j,
// len[currRow][j] stores length of longest
// common substring in string X[0..i] and Y[0..j].
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
len[currRow][j] = 0;
}
else if (X[i - 1] == Y[j - 1]) {
len[currRow][j] = len[1 - currRow][j - 1] + 1;
result = max(result, len[currRow][j]);
}
else {
len[currRow][j] = 0;
}
}
// Make current row as previous row and previous
// row as new current row.
currRow = 1 - currRow;
}
return result;
}
int main()
{
string X = "GeeksforGeeks";
string Y = "GeeksQuiz";
cout << LCSubStr(X, Y);
return 0;
}
// Space optimized CPP implementation of
// longest common substring.
import java.io.*;
import java.util.*;
public class GFG {
// Function to find longest
// common substring.
static int LCSubStr(String X, String Y)
{
// Find length of both the strings.
int m = X.length();
int n = Y.length();
// Variable to store length of longest
// common substring.
int result = 0;
// Matrix to store result of two
// consecutive rows at a time.
int [][]len = new int[2][n];
// Variable to represent which row of
// matrix is current row.
int currRow = 0;
// For a particular value of
// i and j, len[currRow][j]
// stores length of longest
// common substring in string
// X[0..i] and Y[0..j].
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
len[currRow][j] = 0;
}
else if (X.charAt(i - 1) ==
Y.charAt(j - 1))
{
len[currRow][j] =
len[(1 - currRow)][(j - 1)]
+ 1;
result = Math.max(result,
len[currRow][j]);
}
else
{
len[currRow][j] = 0;
}
}
// Make current row as previous
// row and previous row as
// new current row.
currRow = 1 - currRow;
}
return result;
}
// Driver Code
public static void main(String args[])
{
String X = "GeeksforGeeks";
String Y = "GeeksQuiz";
System.out.print(LCSubStr(X, Y));
}
}
// This code is contributed by
// Manish Shaw (manishshaw1)
# Space optimized Python3 implementation
# of longest common substring.
import numpy as np
# Function to find longest common substring.
def LCSubStr(X, Y) :
# Find length of both the strings.
m = len(X)
n = len(Y)
# Variable to store length of
# longest common substring.
result = 0
# Matrix to store result of two
# consecutive rows at a time.
len_mat = np.zeros((2, n))
# Variable to represent which row
# of matrix is current row.
currRow = 0
# For a particular value of i and j,
# len_mat[currRow][j] stores length of
# longest common substring in string
# X[0..i] and Y[0..j].
for i in range(m) :
for j in range(n) :
if (i == 0 | j == 0) :
len_mat[currRow][j] = 0
elif (X[i - 1] == Y[j - 1]) :
len_mat[currRow][j] = len_mat[1 - currRow][j - 1] + 1
result = max(result, len_mat[currRow][j])
else :
len_mat[currRow][j] = 0
# Make current row as previous row and
# previous row as new current row.
currRow = 1 - currRow
return result
# Driver Code
if __name__ == "__main__" :
X = "GeeksforGeeks"
Y = "GeeksQuiz"
print(LCSubStr(X, Y))
# This code is contributed by Ryuga
// Space optimized C# implementation
// of longest common substring.
using System;
using System.Collections.Generic;
class GFG {
// Function to find longest
// common substring.
static int LCSubStr(string X, string Y)
{
// Find length of both the strings.
int m = X.Length;
int n = Y.Length;
// Variable to store length of longest
// common substring.
int result = 0;
// Matrix to store result of two
// consecutive rows at a time.
int [,]len = new int[2,n];
// Variable to represent which row of
// matrix is current row.
int currRow = 0;
// For a particular value of
// i and j, len[currRow][j]
// stores length of longest
// common substring in string
// X[0..i] and Y[0..j].
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
len[currRow,j] = 0;
}
else if (X[i - 1] == Y[j - 1]) {
len[currRow,j] = len[(1 - currRow),
(j - 1)] + 1;
result = Math.Max(result, len[currRow, j]);
}
else
{
len[currRow,j] = 0;
}
}
// Make current row as previous
// row and previous row as
// new current row.
currRow = 1 - currRow;
}
return result;
}
// Driver Code
public static void Main()
{
string X = "GeeksforGeeks";
string Y = "GeeksQuiz";
Console.Write(LCSubStr(X, Y));
}
}
// This code is contributed by
// Manish Shaw (manishshaw1)
<?php
// Space optimized PHP implementation
// of longest common substring.
// Function to find
// longest common substring.
function LCSubStr($X, $Y)
{
// Find length of
// both the strings.
$m = strlen($X);
$n = strlen($Y);
// Variable to store length
// of longest common substring.
$result = 0;
// Matrix to store result of two
// consecutive rows at a time.
$len = array(array(), array(), );
// Variable to represent which
// row of matrix is current row.
$currRow = 0;
// For a particular value of
// i and j, len[currRow][j]
// stores length of longest
// common substring in string
// X[0..i] and Y[0..j].
for ($i = 0; $i <= $m; $i++)
{
for ($j = 0; $j <= $n; $j++)
{
if ($i == 0 || $j == 0)
{
$len[$currRow][$j] = 0;
}
else if ($X[$i - 1] == $Y[$j - 1])
{
$len[$currRow][$j] =
$len[1 - $currRow][$j - 1] + 1;
$result = max($result,
$len[$currRow][$j]);
}
else
{
$len[$currRow][$j] = 0;
}
}
// Make current row as
// previous row and previous
// row as new current row.
$currRow = 1 - $currRow;
}
return $result;
}
// Driver Code
$X = "GeeksforGeeks";
$Y = "GeeksQuiz";
print (LCSubStr($X, $Y));
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
<script>
// Space optimized CPP implementation of longest
// common substring.
// Function to find longest common substring.
function LCSubStr(X, Y)
{
// Find length of both the strings.
var m = X.length;
var n = Y.length;
// Variable to store length of longest
// common substring.
var result = 0;
// Matrix to store result of two
// consecutive rows at a time.
var len = Array.from(Array(2), ()=> Array(n));
// Variable to represent which row of
// matrix is current row.
var currRow = 0;
// For a particular value of i and j,
// len[currRow][j] stores length of longest
// common substring in string X[0..i] and Y[0..j].
for (var i = 0; i <= m; i++) {
for (var j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
len[currRow][j] = 0;
}
else if (X[i - 1] == Y[j - 1]) {
len[currRow][j] = len[1 - currRow][j - 1] + 1;
result = Math.max(result, len[currRow][j]);
}
else {
len[currRow][j] = 0;
}
}
// Make current row as previous row and previous
// row as new current row.
currRow = 1 - currRow;
}
return result;
}
// Driver code
var X = "GeeksforGeeks";
var Y = "GeeksQuiz";
document.write( LCSubStr(X, Y));
// This code is contributed by itsok.
</script>
5
Complexidade de tempo: O (m * n)
Espaço auxiliar: O (n)
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva