Calculación de la subcadena común más larga de dos cadenas usando matrices de sufijo

Question

Después de que aprendí a construir una matriz de sufijo en $ O (n) $ complejidad, estoy interesado en descubrir las aplicaciones de las matrices de sufijo. Una de ellas es encontrar la subcadena común más larga entre dos cuerdas, en $ O (n) $ tiempo. Encontré en Internet el siguiente algoritmo:

1. Fusionar las dos cadenas $ A $ y $ B $ en una cadena $ AB $
2. Calcule la matriz de sufijo de $ AB $
3. Calcule la matriz de $ LCP $ (prefijo común más largo)
4. La respuesta es el mayor valor $ lcp [i] $

Traté de implementarlo, pero como no se dijeron muchos detalles de implementación (es decir, al concatenar las cadenas, ¿debería poner un carácter especial entre ellos ($ acb $)?), Mi código falló en muchos casos de prueba. ¿Alguien podría elaborar más sobre este algoritmo?

Gracias por adelantado.

Nota: No garantizo la corrección de este algoritmo; Lo encontré en un blog y no estoy seguro de que esté funcionando. Si cree que es incorrecto, sugiera otro algoritmo.

Answer 1

Tu algoritmo es incorrecto. Supongo que sabe cómo calcular la matriz de sufijo y la matriz LCP de una cadena, es decir, su implementación eficiente. Como se ha señalado en los comentarios, debe intentar comprender qué es cada componente y por qué funciona.

En primer lugar, es la matriz de sufijo ($ sa $) de una cadena. Una matriz de sufijo es básicamente todos los sufijos de la cadena $ S $ organizado en orden lexicográfica ascendente. Más específicamente, el valor $ sa [i] $ indica que el sufijo de $ S $ a partir de la posición $ sa [i] $ está clasificado $ i $ en el orden lexicográfico de todos los sufijos de $ S $.

El siguiente es el $ LCP $ Array. $ Lcp [i] $ indica la longitud del más largo común prefijo Entre los sufijos A partir de $ sa [i-1] $ y $ sa [i] $. Es decir, realiza un seguimiento de la longitud del prefijo común más largo entre dos sufijos consecutivos de $ S $ cuando se organiza en orden lexicográfico.

Como ejemplo, considere la cadena $ S = Abbabca $. Los sufijos en orden lexicográfico serían $ {a, Abbabca, ABCA, BABCA, BBABCA, BCA, CA } $, entonces $ SA = [7, 1, 4, 3, 2, 5, 6] $ por un 1 -Antle de matriz indexada. La matriz $ LCP $ sería $ lcp = [-, 1, 2, 0, 1, 1, 0] $.

Ahora, dadas dos cadenas $ A $ y $ B $, las concatenamos como $ S = A #B $, donde $ #$ es un personaje que no está presente en $ A $ y $ B $. La razón para elegir dicho personaje es que al calcular el LCP de dos sufijos, digamos $ AB##DABD $ y $ ABD $, la comparación se romperá al final de la primera cadena (ya que solo ocurre una vez, dos, dos diferentes sufijos nunca lo tendrán en la misma posición), y no "Desbordamiento" en la otra cadena.

Ahora, se puede ver que debería poder ver por qué solo necesita ver valores consecutivos en $ LCP $ Array (el argumento se basa en la contradicción y el hecho de que los sufijos en $ SA $ están en orden lexicográfico). Sigue revisando la matriz $ LCP $ por el valor máximo tal que Los dos sufijos que se comparan no pertenecen a la misma cadena original. Si no pertenecen a la misma cadena original (una comienza en $ A $ y la otra en $ B $), entonces el mayor valor de este tipo es la longitud de la subcadena común más grande.

Como ejemplo, considere $ A = ABCABC $ y $ B = BC $. Entonces, $ S = ABCABC #BC $. Los sufijos ordenados son $ {ABC #BC, ABCABC #BC, BC, BC #BC, BCABC #BC, C, C #BC, CABC #BC } $.
$ begin {align*} sa & = [4, 1, 8, 5, 2, 9, 6, 3, 7] lcp & = [-, 3, 0, 2, 2, 0, 1, 1 , 0] end {align*} $

Ahora, el mayor valor es $ lcp [2] = 3 $, pero es por $ sa [1] $ y $ sa [2] $, los cuales comienzan en la cadena $ A $. Entonces, ignoramos eso. Por otro lado, $ lcp [4] = 2 $ es por $ sa [3] $ (corresponde al sufijo $ bc $ de $ b $) y $ sa [4] $ (correspondiente al sufijo $ bcabc #bc $ de $ a $). Entonces, esta es la subcadena común más larga entre las dos cuerdas. Para obtener la subcadena real, obtienes un largo $ 2 $ (valor del mejor factible $ LCP $) Subcandación que comienza desde $ SA [3] $ o $ SA [4] $, que es $ BC $.

Answer 2

El algoritmo que encontró en línea no es del todo correcto. Como lo mencionó Paresh, fallará en el ejemplo dado por él.

Sin embargo, si se asegura de que al verificar el LCP, solo verifica el LCP de sustras de diferentes cadenas. Por ejemplo, si está encontrando el LCS de las cadenas A y B, entonces debe asegurarse de que las entradas adyacentes de la matriz de sufijo al verificar LCP no sean de la misma cadena.

Más detalles aquí.

Answer 3

Creo que algo como el algoritmo que cita debería funcionar si un personaje que no es parte del conjunto de caracteres se usa como separador, y las matrices de sufijo/prefijo se construyen para excluir Todas las cadenas que contienen el separador, probablemente la intención del diseñador. Esto es básicamente equivalente a construir matrices de sufijo/prefijo para las dos cadenas separadas.

Sería útil para Future Ref. Si publicara un enlace al algoritmo. tenga en cuenta que Wikipedia Tiene el algoritmo para esto en pseudocódigo y muchos otros algoritmos. Y hay implementaciones en la mayoría de los idiomas estándar disponibles en línea.