La idea de Aho-Corasick se usa en casi cualquier lugar donde tenga más de un patrón en cualquier sentido. Después de tener un árbol con enlaces de sufijo (o autómatas completos), puede ejecutar una programación dinámica diferente en él. Algunos problemas:
- Encontrar todas las ocurrencias de todos los patrones en el texto. Es bastante simple si tiene que generarlos todos y no le importa mucho el tiempo de ejecución.
- Encuentra la cantidad total de todas las ocurrencias. Es más difícil porque cada vez que tienes una coincidencia, también debes saltar todos los enlaces de sufijos, pero no quieres hacerlo en tiempo cuadrático. Deberías precalcular algo.
- Modifique el autómata ligeramente en línea activando / desactivando las marcas de terminación, sin dejar de responder preguntas sobre sucesos. Problema de ejemplo: si tiene una sola cadena de pajar, un conjunto de patrones y algunas consultas que habilitan / deshabilitan patrones del conjunto, debe imprimir el número total de coincidencias después de cada consulta. Se puede notar que después de haber procesado el pajar, la respuesta es una simple suma ponderada de cantidades de cadenas que terminan en cada vértice del trie. Calcula estos pesos y cada solicitud de cambio se vuelve trivial para responder.
- Agregue árboles de segmentos con una descomposición muy ligera del árbol de enlaces de sufijos y procese todas las ocurrencias que terminan en la misma posición más rápido. No recuerde ningún problema “realista” que lo necesitara.
- Encuentre la cadena lexicográficamente más pequeña que contiene todos los patrones dentro de ella (DP con submáscaras).
- Encuentre la cadena más larga que no contenga ninguno de los patrones y verifique si es finita.