Dadas n cadenas, ¿una de ellas es una subcadena de otra?

Supongamos que se nos da una colección de cadenas, . Me gustaría saber si alguna de esas cadenas es una subcadena de cualquier otra cadena de la colección. En otras palabras, me gustaría un algoritmo para la siguiente tarea: $n$ $S_1,\dots,S_n$

Entrada: $S_1,\dots,S_n$

Salida: tal que es una subcadena de y , o Ninguno si hay tal existen $i,j$ $S_i$ $S_j$ $i\ne j$ $i,j$

¿Existe un algoritmo eficiente para esto?

Si reemplazamos "subcadena" por "prefijo", hay un algoritmo eficiente (clasifique las cadenas, luego realice un escaneo lineal para comparar cadenas adyacentes; la clasificación asegurará que las subcadenas sean adyacentes). Pero parece más difícil probar si alguna cadena es una subcadena de cualquier otra cadena. Un algoritmo ingenuo es iterar sobre todos los pares , pero esto requiere pruebas de subcadena . ¿Hay un algoritmo más eficiente? $i,j$ $\Theta(n^2)$

Supongo que podríamos llamar a esto "prueba de subcadena de todos los pares", o algo así.

Mi objetivo final es podar la colección para que ninguna cadena sea una subcadena de ninguna otra, eliminando cada una que sea una subcadena de otra cosa en la colección.

Sugerencia: matriz de sufijos.

Seudónimo el

Como nota al margen, no es correcto si elimina las subcadenas a medida que las encuentra. Será menos Además, debe ordenar por longitud ya que una cadena más larga no puede aparecer en una cadena más corta. De nuevo, está mal aquí.

Θ (n^{2})

$\Theta(n^2)$

Θ (n^{2})

$\Theta(n^2)$

Alexis Wilke

@AlexisWilke, es correcto: esa es la cantidad de pruebas de subcadenas en el peor de los casos (el peor de los casos es donde ninguna cadena es una subcadena de ninguna otra). Ordenar por longitud solo te da un factor de dos, que no afecta a los asintóticos.

Θ (n^{2})

$\Theta(n^2)$

Respuestas:

Puede construir un árbol de sufijos en tiempo lineal y verificar si hay un nodo interno que corresponde a una cadena completa (tiempo constante por nodo).

Con más detalle, suponga que se nos dan las cadenas . $s_1, \dots, s_n \in \Sigma^*$

Construya un árbol de sufijos (generalizado) de con marcadores terminales distintos por pares . $s_1\$_1, s_2\$_2, \dots, s_n\$_n$ $n$ $\$_1,\dots,\$_n \notin \Sigma$

Usando el algoritmo de Ukkonen , esto se puede hacer en tiempo lineal; lineal en la suma de todas las longitudes de cadena.
Suponiendo que etiqueta las hojas con si representan el sufijo de , recorra el árbol y encuentre esas hojas etiquetadas $(i,j)$ $s_i[j..|s_i|]$ $s_i$ $n$ , es decir, las hojas que corresponden al total instrumentos de cuerda. $(i,0)$

Esto lleva un tiempo lineal en el tamaño del árbol, que es lineal en el tamaño de entrada.
Las hojas descendientes del padre de (que se alcanza mediante un borde etiquetado como ) representan todas las coincidencias del conjunto; Esto se desprende de la invariante básica de los árboles de sufijos. Encuentre cualquier coincidencia descendiendo a cualquier hoja (pero ). $(i,0)$ $\$_i$ $(i,0)$

Esto nuevamente toma tiempo lineal.

Los distintos marcadores terminales no son realmente necesarios; una sola utilizada para terminar todas las cadenas es suficiente siempre que permita múltiples etiquetas por hoja.

Rafael
fuente