En el mundo del procesamiento de texto, bioinformática y análisis de datos, encontrar la subcadena común más larga (LCS) entre dos cadenas es una tarea fundamental. A diferencia del Longest Common Subsequence (LCSq), que permite caracteres no contiguos, la subcadena común más larga exige que los caracteres estén contiguos en ambas secuencias.

Este artículo ofrece una visión profunda del algoritmo, su implementación en Python, comparativas con otras técnicas, consideraciones de rendimiento y ejemplos del mundo real.

1️⃣ Implementación clásica con Programación Dinámica

El algoritmo construye una tabla dp donde dp[i][j] representa la longitud de la subcadena común que termina en str1[i-1] y str2[j-1].

def longest_common_substring_dp(str1: str, str2: str) -> str:
    n, m = len(str1), len(str2)
    # Matriz de (n+1) x (m+1) inicializada a 0
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    longest_len = 0
    longest_end = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > longest_len:
                    longest_len = dp[i][j]
                    longest_end = i  # posición final en str1
            # else: dp[i][j] queda 0 (implícito)
    return str1[longest_end - longest_len: longest_end]
# Ejemplo de uso
s1 = "abracadabra"
s2 = "cadabraz"
print(longest_common_substring_dp(s1, s2))  # salida: "cadabra"

Esta versión ocupa O(n·m) memoria. Para cadenas de varios miles de caracteres puede resultar costosa.

2️⃣ Optimización de espacio: una sola fila

Observando que sólo se necesita la fila anterior, podemos reducir el uso de memoria a O(min(n,m)):

def longest_common_substring_dp_optimized(str1: str, str2: str) -> str:
    # Aseguramos que str2 sea la más corta para minimizar la fila
    if len(str1) < len(str2):
        str1, str2 = str2, str1
    previous = [0] * (len(str2) + 1)
    longest_len = 0
    longest_end = 0
    for i, ch1 in enumerate(str1, 1):
        current = [0]
        for j, ch2 in enumerate(str2, 1):
            if ch1 == ch2:
                val = previous[j - 1] + 1
                current.append(val)
                if val > longest_len:
                    longest_len = val
                    longest_end = i
            else:
                current.append(0)
        previous = current
    return str1[longest_end - longest_len: longest_end]

Esta variante mantiene la claridad del algoritmo y permite procesar textos de decenas de miles de caracteres sin superar los 10 MB de RAM.

3️⃣ Solución lineal con Suffix Tree (Ukkonen)

Para volúmenes masivos (millones de caracteres) la complejidad O(n+m) del árbol de sufijos es decisiva. Python no incluye una implementación nativa, pero podemos usar la librería pysuffix o treelib. A continuación, un ejemplo usando pysuffix:

# pip install pysuffix
from pysuffix import SuffixTree
def longest_common_substring_suffix_tree(s1: str, s2: str) -> str:
    # Concatenamos con un separador que no aparezca en los textos
    sep = '#'
    while sep in s1 or sep in s2:
        sep = chr(ord(sep) + 1)
    combined = s1 + sep + s2
    tree = SuffixTree(combined)
    # Cada nodo guarda la longitud del substring más largo que aparece en ambas partes
    max_len = 0
    max_sub = ''
    for node in tree.nodes:
        if node.depth > max_len:
            # Verificamos que el nodo contiene al menos una hoja de cada cadena
            leaves = node.leaf_indices()
            has_s1 = any(idx < len(s1) for idx in leaves)
            has_s2 = any(idx > len(s1) for idx in leaves)
            if has_s1 and has_s2:
                max_len = node.depth
                max_sub = combined[node.start: node.start + max_len]
    return max_sub
print(longest_common_substring_suffix_tree('banana', 'ananas'))  # salida: 'anana'

Ventajas:

• Escalabilidad lineal.
• Permite consultas posteriores (p.ej., encontrar todas las subcadenas comunes).

Desventajas:

• Implementación más compleja.
• Requiere librerías externas o código propio.

4️⃣ Alternativa ligera: Suffix Automaton (SAM)

El automáta de sufijos ofrece la misma complejidad lineal con una construcción más sencilla que el árbol. A continuación, una versión compacta en Python:

class State:
    __slots__ = ('next', 'link', 'len')
    def __init__(self):
        self.next = {}
        self.link = -1
        self.len = 0
def build_suffix_automaton(s: str):
    st = [State()]  # estado 0 = raíz
    last = 0
    for ch in s:
        cur = len(st)
        st.append(State())
        st[cur].len = st[last].len + 1
        p = last
        while p >= 0 and ch not in st[p].next:
            st[p].next[ch] = cur
            p = st[p].link
        if p == -1:
            st[cur].link = 0
        else:
            q = st[p].next[ch]
            if st[p].len + 1 == st[q].len:
                st[cur].link = q
            else:
                clone = len(st)
                st.append(State())
                st[clone].len = st[p].len + 1
                st[clone].next = st[q].next.copy()
                st[clone].link = st[q].link
                while p >= 0 and st[p].next.get(ch) == q:
                    st[p].next[ch] = clone
                    p = st[p].link
                st[q].link = st[cur].link = clone
        last = cur
    return st
def longest_common_substring_sam(s1: str, s2: str) -> str:
    automaton = build_suffix_automaton(s1)
    v = 0  # estado actual
    l = 0  # longitud actual de coincidencia
    best = 0
    best_pos = 0
    for i, ch in enumerate(s2):
        while v and ch not in automaton[v].next:
            v = automaton[v].link
            l = automaton[v].len
        if ch in automaton[v].next:
            v = automaton[v].next[ch]
            l += 1
        if l > best:
            best = l
            best_pos = i
    return s2[best_pos - best + 1: best_pos + 1]
print(longest_common_substring_sam('abracadabra', 'cadabraz'))  # salida: 'cadabra'

El SAM es particularmente útil cuando se necesita procesar múltiples consultas contra la misma cadena base (por ejemplo, buscar subcadenas comunes contra un diccionario grande).

5️⃣ Casos de uso del mundo real

• Detección de plagio en documentos académicos: comparar el texto del estudiante contra una base de documentos.
• Bioinformática: hallar la mayor coincidencia entre dos secuencias de ADN o proteínas.
• Compresión de datos: identificar bloques repetidos para generar diccionarios de compresión.
• Seguridad informática: comparar firmas de malware para detectar variantes.

En todos estos escenarios, la elección entre DP, Suffix Tree o SAM depende del tamaño de los datos y si se repetirán consultas.

6️⃣ Buenas prácticas, depuración y seguridad

Validación de entrada

Siempre verifica que los parámetros sean str y que no contengan caracteres de control que puedan romper la lógica (p.ej., \0). Un ejemplo sencillo:

def safe_str(s):
    if not isinstance(s, str):
        raise TypeError('Se espera una cadena de texto')
    return s.replace('\0', '')

Gestión de memoria en grandes volúmenes

• Usa la variante de una sola fila cuando n·m supere 10⁸ para evitar MemoryError.
• En entornos con limitaciones de RAM, considera procesar los textos por bloques (windowing) y combinar resultados.

Depuración

Imprime la tabla dp solo en modo debug para confirmar la lógica:

import pprint
if __debug__:
    pprint.pprint(dp)

Seguridad

Si recibes texto de usuarios externos, sanitiza antes de concatenar separadores en la versión de árbol de sufijos para evitar que el separador colisione con el contenido y produzca resultados erróneos.

7️⃣ Benchmark rápido (CPU) – DP vs. SAM vs. Suffix Tree

import time, random, string
def rand_str(n):
    return ''.join(random.choices(string.ascii_lowercase, k=n))
s1 = rand_str(200_000)
s2 = s1[:100_000] + rand_str(100_000)  # 100k de coincidencia al inicio
# DP (optimizada)
start = time.time()
longest_common_substring_dp_optimized(s1, s2)
print('DP optimizado:', time.time() - start)
# SAM
start = time.time()
longest_common_substring_sam(s1, s2)
print('SAM:', time.time() - start)
# Suffix Tree (pysuffix) – solo para comparación, puede ser más lento en Python puro
# start = time.time()
# longest_common_substring_suffix_tree(s1, s2)
# print('Suffix Tree:', time.time() - start)

En máquinas modernas, el SAM suele ser 2‑3× más rápido que la DP optimizada para 200 k caracteres, mientras que la versión de árbol de sufijos puede requerir una implementación en C para competir.