Supongamos que tengo un conjunto de cadenas S y una cadena de consulta q. Quiero saber si algún miembro de S es una subcadena de q. (A los efectos de esta pregunta subcadena incluye la igualdad, por ejemplo, "foo" es una subcadena de "foo"). Por ejemplo asume la función que hace lo que yo quiero que se llama anySubstring
:Estructura de datos eficiente para la búsqueda de subcadenas?
S = ["foo", "baz"]
q = "foobar"
assert anySubstring(S, q) # "foo" is a substring of "foobar"
S = ["waldo", "baz"]
assert not anySubstring(S, q)
¿Hay alguna fácil- implementar algoritmo para hacer esto con complejidad de tiempo sublineal en len(S)
? Está bien si S tiene que procesarse primero en una estructura de datos inteligente porque voy a consultar cada S con muchas cadenas q, por lo que el costo amortizado de este preproceso podría ser razonable.
EDITAR: Para aclarar, no me importa que miembro de S es una subcadena de q, solo si al menos uno es. En otras palabras, I solo se preocupan por una respuesta booleana.
¿Las cadenas en S son cortas? ¿Cómo se compara la longitud de la cuerda más larga en S con la longitud de S? – aelguindy