Extensión común más larga / LCE | Conjunto 1 (Introducción y Método Ingenuo)

El problema de la extensión común más larga (LCE) considera una string s y calcula, para cada par (L , R), la substring más larga de s que comienza tanto en L como en R. En LCE, en cada una de las consultas que tenemos que responder la longitud del prefijo común más largo que comienza en los índices L y R.

Ejemplo:  
String : “abbababba” 
Consultas: LCE(1, 2), LCE(1, 6) y LCE(0, 5) 

Encuentre la longitud del prefijo común más largo que comienza en el índice dado como (1, 2), (1, 6) y (0, 5) .
La string resaltada es el prefijo común más largo que comienza en el índice L y R de las consultas respectivas. Tenemos que encontrar la longitud del prefijo común más largo que comienza en index- (1, 2), (1, 6) y (0, 5) .

 Algoritmo (método ingenuo)

1. Para cada una de las consultas LCE del formulario – LCE(L, R) haga lo siguiente: 
   • Inicialice la ‘longitud’ de LCE como 0
   • Comience a comparar el prefijo a partir del índice: L y R carácter por carácter.
   • Si los caracteres coinciden, entonces este carácter está en nuestra extensión común más larga. Entonces incremente ‘longitud’ (longitud ++).
   • De lo contrario, si los caracteres no coinciden, devuelva esta ‘longitud’.
2. La ‘longitud’ devuelta será el LCE (L, R) requerido.

Implementación: 

A continuación se muestra la implementación en C++ del algoritmo Naive anterior. 

// A C++ Program to find the length of longest
// common extension using Naive Method
#include<bits/stdc++.h>
using namespace std;
 
// Structure to represent a query of form (L,R)
struct Query
{
    int L, R;
};
 
// A utility function to find longest common
// extension from index - L and index - R
int LCE(string str, int n, int L, int R)
{
    int length = 0;
 
    while (str[L+length] == str[R+length] &&
            R+length < n)
        length++;
 
    return(length);
}
 
// A function to answer queries of longest
// common extension
void LCEQueries(string str, int n, Query q[],
                                       int m)
{
    for (int i=0; i<m; i++)
    {
        int L = q[i].L;
        int R = q[i].R;
 
        printf("LCE (%d, %d) = %d\n", L, R,
                         LCE(str, n, L, R));
    }
    return;
}
 
// Driver Program to test above functions
int main()
{
    string str = "abbababba";
    int n = str.length();
 
    // LCA Queries to answer
    Query q[] = {{1, 2}, {1, 6}, {0, 5}};
    int m = sizeof(q)/sizeof(q[0]);
 
    LCEQueries(str, n, q, m);
 
    return (0);
}

// A Java Program to find the length of longest
// common extension using Naive Method
import java.util.*;
class GFG
{
 
// Structure to represent a query of form (L,R)
static class Query
{
    int L, R;
    Query(int L, int R)
    {
        this.L = L;
        this.R = R;
    }
};
 
// A utility function to find longest common
// extension from index - L and index - R
static int LCE(String str, int n, int L, int R)
{
    int length = 0;
    while ( R + length < n && str.charAt(L + length) == str.charAt(R + length))
        length++;
    return(length);
}
 
// A function to answer queries of longest
// common extension
static void LCEQueries(String str, int n, Query q[],
                                       int m)
{
    for (int i = 0; i < m; i++)
    {
        int L = q[i].L;
        int R = q[i].R;
        System.out.printf("LCE (%d, %d) = %d\n", L, R,
                         LCE(str, n, L, R));
    }
    return;
}
 
// Driver code
public static void main(String[] args)
{
    String str = "abbababba";
    int n = str.length();
 
    // LCA Queries to answer
    Query q[] = new Query[3];
    q[0] = new Query(1, 2);
    q[1] = new Query(1, 6);
    q[2] = new Query (0, 5);
    int m = q.length;
    LCEQueries(str, n, q, m);
}
}
 
// This code is contributed by gauravrajput1

// A C# Program to find the length of longest
// common extension using Naive Method
using System;
public class GFG
{
 
  // Structure to represent a query of form (L,R)
  public
    class Query
    {
      public
        int L, R;
      public
        Query(int L, int R)
      {
        this.L = L;
        this.R = R;
      }
    };
 
  // A utility function to find longest common
  // extension from index - L and index - R
  static int LCE(String str, int n, int L, int R)
  {
    int length = 0;
    while ( R + length < n && str[L + length] == str[R + length])
      length++;
    return(length);
  }
 
  // A function to answer queries of longest
  // common extension
  static void LCEQueries(String str, int n, Query []q,
                         int m)
  {
    for (int i = 0; i < m; i++)
    {
      int L = q[i].L;
      int R = q[i].R;
      Console.WriteLine("LCE (" + L + ", " + R +
                        ") = " + LCE(str, n, L, R));
    }
    return;
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    String str = "abbababba";
    int n = str.Length;
 
    // LCA Queries to answer
    Query []q = new Query[3];
    q[0] = new Query(1, 2);
    q[1] = new Query(1, 6);
    q[2] = new Query (0, 5);
    int m = q.Length;
    LCEQueries(str, n, q, m);
  }
}
 
// This code is contributed by Rajput-Ji

<script>
// A Javascript Program to find the length of longest
// common extension using Naive Method
 
// Structure to represent a query of form (L,R)
class Query
{
    constructor(L,R)
    {
        this.L = L;
        this.R = R;
    }
}
 
// A utility function to find longest common
// extension from index - L and index - R
function LCE(str,n,L,R)
{
    let length = 0;
    while ( R + length < n && str[L + length] == str[R + length])
        length++;
    return(length);
}
 
// A function to answer queries of longest
// common extension
function LCEQueries(str,n,q,m)
{
    for (let i = 0; i < m; i++)
    {
        let L = q[i].L;
        let R = q[i].R;
        document.write("LCE ("+L+", "+R+") = "+LCE(str, n, L, R)+"<br>");
    }
    return;
}
 
// Driver code
let  str = "abbababba";
let n = str.length;
 
// LCA Queries to answer
let q = new Array(3);
q[0] = new Query(1, 2);
q[1] = new Query(1, 6);
q[2] = new Query (0, 5);
let m = q.length;
LCEQueries(str, n, q, m);
 
// This code is contributed by unknown2108
</script>

LCE (1, 2) = 1
LCE (1, 6) = 3
LCE (0, 5) = 4

Análisis del Método Ingenuo  :

Complejidad del tiempo: La complejidad del tiempo es O(QN), donde 

• Q = Número de consultas LCE 
• N = Longitud de la string de entrada 

Uno puede sorprenderse de que, aunque tiene una mayor complejidad de tiempo asintótico, el método ingenuo supera a otros métodos eficientes (asintóticamente) en usos prácticos. Discutiremos esto en los próximos sets sobre este tema.

Espacio auxiliar: O(1), algoritmo in situ.

Aplicaciones: 

1. Problema de desajuste K->Landau-Vishkin usa LCE como una subrutina para resolver el problema de desajuste k
2. Búsqueda aproximada de strings.
3. Emparejamiento palíndromo con comodines.
4. Alineación global de diferencia K.

En los siguientes conjuntos, discutiremos cómo el problema LCE (extensión común más larga) se puede reducir a una RMQ (consulta de rango mínimo). También discutiremos métodos más eficientes para encontrar la extensión común más larga.

Este artículo es una contribución de Rachit Belwariar . 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.