Trie & subsequences

Question

Tenemos dos juegos, A y B. Cada uno de estos conjuntos incluye cadenas. ej .: A - {"abwcd", "dwas", "www"} y B - {"opqr", "tops", "ibmd"} ¿Cómo puedo contar las subsecuencias que aparecen en todas las cadenas del conjunto A? , pero en ninguna de las cuerdas del conjunto B? Para el ejemplo anterior, la respuesta es 1 (la subsecuencia "w").

Todo esto de una manera óptima. Pensé en usar dos intentos, la primera vez puse todas las subsecuencias de todas las cadenas en B en trie t_B y luego, comienzo a poner todas las subsecuencias de todas las cadenas en A en el trie t_A, sin actualizar el trie si es el mismo subsecuencia se encontró antes en la misma cadena (por ejemplo: si tengo la cadena "aba", no cuento la subsecuencia "a" dos veces). De esta forma, si encuentro una subsecuencia que tiene n (tamaño de A) apariencias en t_A, verifico si está en t_B, y si no lo está, lo cuento. Pero esto es muy, muy lento, si A y B tienen el tamaño 15 y las cadenas tienen alrededor de 100 caracteres, mis programas se ejecutan en más de 1 segundo.

EDIT: Desde cualquier subsqeunce termina en el último carácter de la cadena o en un personaje que conoce, que no tenemos que ge todas las subsecuencias, pero los que terminan en el último carácter de la cadena. Cuando los empujo al trie, noto que cada nodo tiene 1. Entonces, si tengo la cadena "abcd", solo presiono "abcd", "bcd", "cd" y "d", ya que este debería ser el ' esqueleto 'del trie. Pero esta no es una optimización muy grande, todavía estoy buscando algo mejor.

Answer 1

No debería tener que poner todas las subsecuencias de todas las cadenas en A en el trie. Solo ingrese los válidos. Pruebe si una secuencia es válida antes de agregarla. Supongo que una prueba de membresía es más rápida que agregar un nuevo elemento. Un trie más pequeño debe fallar las pruebas de membresía más rápido, por lo que esta estrategia está diseñada para recortar el trie lo más rápido posible.

Específicamente: Coloque todas las subsecuencias de la primera cadena en A en el trie. (Para mayor eficiencia, use la cadena más corta como la primera). Mantenga un conjunto de referencias a todos los nodos de hoja. A continuación, para todas las cadenas en B, pruebe cada subsecuencia para ver si existe en A. Si lo hace, elimine esa secuencia y su referencia. (Comience con la cuerda más larga en B para cortar el trie lo más rápido posible).

Ahora tiene el conjunto mínimo de posibilidades para probar. Para todas las cadenas restantes en A, pruebe cada subsecuencia para ver si existe en el trie. Si lo hace, marque el nodo como válido, de lo contrario, vaya a la subsecuencia siguiente. Después de cada cadena, elimine todos los nodos inválidos del trie y restablezca los indicadores en el resto como inválidos.