Supersecuencia de una bolsa de cuerdas

Dada una cadena s, ¿cuál es la forma más eficiente de identificar la supersecuencia más corta de s de una bolsa de cuerdas? Además, el último carácter de s debe coincidir con el último carácter de la supercuerda.Supersecuencia de una bolsa de cuerdas

Fuente

2011-12-14 Vikram Bodicherla

Qué quiere decir, que tiene una bolsa como '{ "abbc", "abbbbb", "ba"}' y una cadena como ' "BB" 'y quiere descubrir que' "abbc" 'es el la supercuerda más corta de '" bb "' en la bolsa? Puede hacer esto en 'O (| s |)' si almacena sus cadenas en una estructura de datos adecuada. –

No del todo @ThomasAhle, en su ejemplo, la salida debe ser 'abbbbb' porque la BB y la salida deben tener el mismo último carácter. –

Ok, entonces el 's' tiene que ser un postfijo. Y con '{" abb "," abba "," aabb "," a "}' la respuesta sería '" abb "', ¿verdad? Eso hará que el problema sea aún más fácil. –

A menos que no he entendido bien, este problema es con toda seguridad en P.

Un enfoque ingenuo sería:

Tome todas las cadenas en B que terminan en s mismo carácter que. Llame a esta nueva bolsa B '. Se puede hacer en O (| B |)
Seleccione todas las cadenas que son supersecuencias de s en la bolsa B '. Se puede hacer en O (| B '| * max (| z |)) para z en B. Pruebas de si una determinada cadena s es una subsecuencia de otra cadena z se puede hacer en O (| z |)
Seleccione el más corto de los que anteriormente se encontraban cuerdas (en O (| B '|))

Dónde | x | significa tamaño de x.

Se pueden combinar esos pasos, pero es O (| B | * max (| z |)) de todos modos.

Fuente

2011-12-14 20:30:04 soulcheck

¿Qué pasa si no hay cadenas en la bolsa que son supersecuencias de las cuerdas que terminan en algún personaje? Si no hay uno, no puede enumerar todas las cadenas posibles en tiempo polinomial, ya que hay muchas de ellas exponencialmente. – templatetypedef

@templatetypedef, entonces la respuesta es 'tal supersecuencia no existe'. OP está buscando la supersecuencia de una cadena dada en la bolsa, eso también se da. Si él no lo encuentra, que así sea. – soulcheck

¡Vaya! ¡Leí mal la pregunta! Pensé que OP estaba pidiendo encontrar, dada una bolsa de hilos, la supersecuencia más corta de la bolsa. Ese problema es NP-difícil. La verdadera pregunta no es muy difícil. ¡Mis disculpas! – templatetypedef

Suponiendo que la bolsa no cambia muy a menudo, me gustaría construir un DAWG y buscarla con A *.

Fuente

2011-12-14 16:51:24 Per

Ejecutar a través de cada cadena en la bolsa, comprobando si s es una subcadena utilizando una cadena de búsqueda rápida como KMP. Comprueba cuál de las supercuerdas es la más corta. Esto es O(Σlength of strings in bag).

Si necesita hacer la búsqueda un múltiplo de veces, se puede construir un trie de sufijo para cada cadena en la bolsa, y combinar estos. Luego puede hacer búsquedas en O(|s|).

Fuente

2011-12-15 01:03:48

Supersecuencia de una bolsa de cuerdas

Respuesta

Cuestiones relacionadas