Encontrar la subsecuencia repetitiva más larga

Dada una cadena $s$ , me gustaría encontrar la subsecuencia de repetición más larga (al menos dos veces). Es decir, me gustaría encontrar una cadena que sea una subsecuencia (no tiene que ser contigua) de tal que . Es decir, es una cadena cuyas mitades aparecen dos veces seguidas. Tenga en cuenta que es una subsecuencia de , pero no necesariamente una subcadena. $w$ $s$ $w=w' \cdot w'$ $w$ $w$ $s$

Ejemplos:

Para 'ababccabdc' será 'abcabc', porque 'abc' = 'abc' y 'abc' aparecen (al menos) dos veces en 'ababccabdc'.

Para 'addbacddabcd' una opción es 'dddd' porque 'dd' aparece dos veces (no puedo usar la misma letra varias veces, pero aquí tengo 4 'd's así que está bien), pero es de longitud 4. Puedo encontrar una mejor de longitud 8: 'abcdabcd', porque 'abcd' es una subcadena de 'addbacddabcd' que aparece dos veces.

Estoy interesado en encontrar la subsecuencia repetitiva más larga. Esto también se llama "encontrar el cuadrado más largo / más grande", pero he leído muchos artículos en los que se define un cuadrado para una subcadena y no para una subsecuencia.

Puedo usar fácilmente un algoritmo de fuerza bruta que tomará iterando en todas las opciones para un punto de interrupción en la cadena, y luego tendré dos cadenas en las que buscaré la subsecuencia común más grande / más larga, pero cada verificación tomará utilizando una técnica de programación dinámica, por lo que todo el tiempo será . Encontré un algoritmo más eficiente para la subsecuencia común más larga que toma , por lo que el tiempo de ejecución será . $O(n^3)$ $O(n^2)$ $O(n^3)$ $O(\frac{n^2}{\log n})$ $O(\frac{n^3}{\log n})$

Estoy buscando un algoritmo más eficiente para el problema de subsecuencia repetitiva más largo. Quizás mi idea de iterar sobre todos los puntos de interrupción desperdicia demasiado tiempo y puede reducirse a menos iteraciones. O quizás un algoritmo con una actitud diferente pueda resolver este problema.

He buscado en muchas revistas y preguntas anteriores, y la mayoría de los resultados que encontré fueron sobre una subcadena y no sobre una subsecuencia.

También he leído que esto se puede hacer usando árboles de sufijos, pero esto también era relevante para las subcadenas y no estoy seguro de si esa idea puede extenderse para la subsecuencia.

Estoy buscando una solución que se ejecute en el tiempo $O(n^2)$ . Si existe uno en el tiempo eso será aún mejor (no estoy seguro de si existe). $O(n \cdot \log n)$

algorithms optimization dynamic-programming strings subsequences Dan D-man
fuente

Busque árboles de sufijos o matrices de sufijos.

Seudónimo

Es muy poco probable que exista un algoritmo de tiempo

para este problema, ya que si lo hiciera, podría usarlo para vencer al algoritmo más conocido para encontrar el LCS de dos cadenas de longitud

siguiente manera: Forma la cadena

, donde

copias de un carácter que no aparece en

, y luego ejecuta su

o (n^{2})

$o(n^2)$

n

$n$

u

$u$

v

$v$

x u x v

$xuxv$

x

$x$

n + 1

$n+1$ $

u

$u$

v

$v$

o (n^{2})

$o(n^2)$ algoritmo de tiempo en él. Ambas "mitades" de la subsecuencia repetitiva más larga necesariamente comenzarán con

, por lo que la mitad proviene de cada uno de

, resolviendo el problema de LCS.

x

$x$

u

$u$

v

$v$

j_random_hacker

@j_random_hacker LCS podría resolverse en

usando Suffix Tree o en

usando hashes rodantes.

O (n + m)

$\mathcal O(n+m)$

O (n \log n)

$\mathcal O(n\log n)$

Evil

@ Mal: todavía no veo cómo, ¿podrías dar un poco más de detalles? (¿Está seguro de que no está pensando en Sub común más larga cadena , que puede ser resuelto en esas complejidades de tiempo?)

j_random_hacker

@j_random_hacker Pensé que estaba comparando el objetivo

con LCS (consecutivo), pero aquí, como mencionó, sí, ni siquiera he visto una solución funcional en n ^ 2 para la subsecuencia común más larga (he encontrado una código de programación dinámico, propagado a través de muchas páginas, que es defectuoso, similar a la respuesta con voto negativo). Así que simplemente no entendí tu comentario, lo siento.

o (n^{2})

$o(n^2)$

Evil

Aquí hay una solución de programación dinámica.

Suponga que la cadena de entrada es . Cree una tabla cuyas filas y columnas estén indexadas por (donde es la longitud de la cadena), poblada por la regla $x_1\ldots x_n$ $T$ $0,\ldots,n$ $n$ La respuesta es.

T [yo, j] = {\begin{cases} 0 0 & Si yo = 0 0 o j = 0 0, \\ T [yo - 1, j - 1] + 1 & Si X_{yo} = X_{j} y yo \neq j, \\ max (T [yo - 1, j], T [yo, j - 1]) & de otra manera . \end{cases}

$T[i,j] = \begin{cases} 0 & \text{if $i = 0$ or $j = 0$}, \\ T[i-1,j-1] + 1 & \text{if $x_i = x_j$ and $i \neq j$}, \\ \max(T[i-1,j],T[i,j-1]) & \text{otherwise}. \end{cases}$

T [n, n]

$T[n,n]$

jir17
fuente

Supongamos que estamos en algún

con

, y la condición en su declaración es verdadera. Entonces implica que el carácter en la posición

es parte de ambas subsecuencias.

i, j

$i, j$

i = j + 1

$i=j+1$ ifdp[i][j] = dp[i - 1][j - 1] + 1

i - 1 = j

$i-1=j$

j_random_hacker

Bienvenido a la informática! Deshágase del código fuente y reemplácelo con ideas, pseudocódigo y argumentos de corrección. Ver aquí y aquí para meta discusiones relacionadas.

Raphael

@Raphael Una fórmula recursiva no cuenta como código fuente.

Número945

@BreakingBenjamin Dependiendo de su idioma de elección, puede escribir la recurrencia dada más o menos literalmente. El punto es que no hay explicación aquí.

Raphael

Encontrar la subsecuencia repetitiva más larga

Respuestas: