Dada una lista de cadenas, encuentre cada par $(x,y)$ donde $x$ es una subcadena de $y$.¿Es posible hacerlo mejor que $O(n^2)$?

Question

Considere el siguiente problema algorítmico:Dada una lista de cadenas $L = [s_1, s_2, \puntos, s_n]$, queremos saber todos los pares $(x,y)$ dónde $x$ es una subcadena de $y$.Podemos asumir que todas las cadenas tienen una longitud máxima $m$, dónde $m << n$ y están por todas partes en un alfabeto finito $\Sigma$ con $|\Sigma| << n$.También podemos suponer que el número de pares $(x,y)$ dónde $x$ es una subcadena de $y$ es mucho más pequeño que $n$.

Un algoritmo trivial sería este:

1. foreach x in L:
2.   foreach y in L:
3.      if x is substring of y:
4.         OUTPUT x,y

Sin embargo, esto tiene complejidad. $O(n^2 \cdot m)$ - Tengo curiosidad por saber si existe un algoritmo más rápido.

Editar:Como se señala en los comentarios, puede haber como máximo $n^2$ tales pares, así que no veo cómo puede haber un algoritmo más rápido que $O(n^2)$.Sin embargo, me preguntaba si hay algo así como un $P-FPT$ algoritmo donde la complejidad al cuadrado depende del número de pares de salida, en lugar de $n$?O al menos un algoritmo que reduzca la complejidad a algo mejor que $O(n^2 \cdot m)$.

Answer 1

Esto se puede solucionar con Algoritmo de Aho-Corasick en $O(nm + Mm)$ tiempo, donde $M$ es el número de pares generados.

Primero construya el autómata Aho-Corasick para el conjunto de cuerdas en $O(nm)$ tiempo.Luego pase cada cuerda a través del autómata; esto requiere $O(nm)$ tiempo para pasar las cuerdas a través del autómata y $O(Mm)$ tiempo para generar las coincidencias porque la misma cadena puede coincidir $m$ veces en el peor de los casos.(Por ejemplo ab partidos ababab 3 veces.)

---

Esto se puede mejorar a verdadero lineal. $O(L+M)$ tiempo, donde $l$ es la longitud total de las cuerdas y $M$ es el número de coincidencias:

Al ejecutar las cadenas a través del autómata, almacene para cada nodo del autómata el índice de la cadena anterior para la cual se visitó este nodo.Al generar las coincidencias, deje de seguir los enlaces del diccionario si el enlace conduce a un nodo que ya ha sido visitado para esta cadena; ya ha generado todas las coincidencias que están hacia arriba desde ese nodo.Ahora cada coincidencia se genera exactamente una vez y recorremos los enlaces del diccionario solo cuando se generan nuevas coincidencias.