Dada una lista de cuerdas, encuentre cada par de $ (x, y) $, donde $ x $ es una subsecuencia de $ y $.Posible hacer mejor que $ O (n ^ 2) $?

Question

Considere el siguiente problema algorítmico: dada una lista de cadenas $ l= [s_1, s_1, \ dots, s_n] $ , queremos conocer todos los pares < Span Class="Math-contenedor"> $ (x, y) $ donde $ x $ es una subsecuencia de $ y $ . Podemos asumir que todas las cadenas son de longitud en el máximo $ m $ , donde $ m << n $ y están en todo un alfabeto finito $ \ sigma $ con $ | \ sigma | << N $ . También podemos asumir que el número de pares $ (x, y) $ donde $ x $ es un La subsecuencia 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 subsequence of y:
4.         OUTPUT x,y

Sin embargo, esto tiene complejidad $ o (n ^ 2 \ cdot m) $ - Tengo curiosidad por saber si hay un algoritmo más rápido (más rápido dado que el Número de pares $ (x, y) $ es mucho más pequeño que $ n $ , por ejemplo, un algoritmo con complejidad dependiendo de la cantidad de pares de salida).

Tenga en cuenta que esta pregunta es un seguimiento para esta pregunta , que trata sobre el mismo problema, pero para las substerias (no posteriores). Allí, el algoritmo AHO-CORASICK resolvió perfectamente mi problema, ¿hay algo así como esto, pero para las subsiguientes?

Answer 1

No, no es posible hacerlo mejor a menos que falle la hipótesis de tiempo exponencial (Seth). Si pudiéramos resolver este problema sustancialmente más rápido que $ o (n ^ 2) $ obtendríamos un algoritmo mucho más rápido para resolver la satisfacción del problema de NP-completa. Esto es cierto incluso para $ m $ ligeramente más que $ \ log (n) $ y el caso en que queremos decidir si un par $ (x, y) $ existe en absoluto.

ver, por ejemplo, estas notas de conferencia bajo la sección 3 " Límites inferiores para vectores ortogonales ". La prueba es análoga a la prueba del teorema 2 en estas notas de la conferencia.

Primero, consideramos el problema más general de dados dos conjuntos de cadenas $ x, y $ , encontrar si algunas cuerdas en $ X $ es una subsecuencia de una cadena en $ y $ .

Dada una fórmula SAT, dividimos su $ n $ variables en dos conjuntos iguales de $ n / 2 $ < / span> variables. En $ \ sigma $ Tomamos un personaje correspondiente a cada cláusula. En $ x $ Agregamos una cadena para cada asignación posible en la primera mitad de las variables, con un personaje correspondiente a cada cláusula no satisfecha por esas variables. Mientras tanto, en $ y $ , agregamos una cadena para cada asignación a la segunda mitad de las variables, con un carácter para cada cláusula satisfecha por esas variables. Claramente, la fórmula es satisfactoria si y solo si alguna cadena en $ x $ es una subsecuencia de alguna cadena en $ y $ .

Si este problema se puede resolver sustancialmente más rápido que $ o (n ^ 2) $ , esto proporciona un algoritmo sustancialmente más rápido para la satisfacción que $ 2 ^ n $ . Supongamos que el problema podría resolverse en $ o (n ^ {1.99}) $ tiempo, entonces la satisfacción podría resolverse en $ (2 ^ {N / 2}) ^ {1.99}= O (2 ^ {0.996n}) $ que contradice el seth.

En su problema, solo hay un solo conjunto de cuerdas, todas las cuales pueden ser una subsecuencia entre sí. Sin embargo, esto no es un problema, ya que podemos simplemente modificar las cadenas en nuestra instancia, de manera que no hay una cadena $ y $ es una subsecuencia de cualquier otra cadena (por ejemplo, por acolchado todas las cuerdas en $ y $ para tener la misma longitud), y al acolchar de manera similar cada cadena en $ x $ a la misma longitud que otras cadenas en $ x $ (pero sustancialmente más corta que las cadenas en $ y $ ) .

Esto también puede hacerse con un alfabeto de tamaño constante (probable incluso binario), pero esto requiere una codificación más inteligente.