Como verifico com eficiência se uma string corresponde a qualquer substring em uma coleção

Eu tenho uma coleção de substrings

"this" "is" "a" "antelope"

Eu preciso olhar para qualquer string e responder à pergunta "Alguma das substrings fornecidas nessa string"

Portanto, minha string de entrada pode ser

"issue"

O que seria uma correspondência porque "is" é uma substring de "issue"

Na minha primeira tentativa, transformou incorretamente minha coleção de substrings em um teste. Isso não me levou a lugar nenhum tão rápido quanto respondeu o inverso "a string de entrada é uma substring da coleção especificada".

Existe algum algoritmo ou estrutura de dados em que posso transformar minha coleção para responder com eficiência a essa pergunta? Quero dizer, eu poderia fazer o método simples de força bruta "verificar a entrada contra cada substring", mas parece que existe uma maneira melhor.

No meu exemplo, eu esperaria que o "antílope" nunca fosse verificado porque "a" cobre todos os casos que o antílope o faria. Posso até esperar que "is" remova "this", pois todos os casos em que "this" encontrariam uma correspondência "são" também o removeriam. Portanto, parece que eliminar substrings mais longos por outros mais curtos produziria um desempenho melhor.

Estou divagando ... Algo que eu deveria estar procurando?

Eu acho que o algoritmo Aho-Corasick é sua melhor aposta aqui. O algoritmo foi projetado para resolver o problema de correspondência de conjuntos (essencialmente o que você definiu), no qual você deseja determinar quais elementos de um conjunto de substrings, L, podem ser encontrados em uma sequência mais longa, S.

É executado no tempo , onde(o comprimento total das subsequências em ), é o comprimento de S, e é o número de jogos de em .$O(n + m + z)$$n = \sum \limits_{l \in L} |l|$$L$$m$$z$$L$$S$