Algoritmo rápido para procurar substrings em uma string
Eu gostaria de um algoritmo eficiente (ou biblioteca) que eu possa usar em Java para procurar substrings em uma string.
O que eu gostaria de fazer é:
Dada uma string de entrada -INSTR:
"BCDEFGH"
E um conjunto de strings candidatas -CAND:
"AB", "CDE", "FG", "H", "IJ"
Encontre algumCAND seqüências de caracteres que correspondem como substrings dentroINSTR
Neste exemplo, eu combinaria "CDE", "FG" e "H" (mas não "AB" e "IJ")
Pode haver muitos milhares de strings candidatas (em CAND), mas o mais importante é que vou fazer essa pesquisa muitos milhões de vezes, então eu preciso que seja FAST.
Eu gostaria de trabalhar com matrizes de caracteres. Além disso, não estou interessado em soluções arquitetônicas, como distribuir a pesquisa - apenas a função / algoritmo mais eficiente para fazer isso localmente.
Além disso, todas as strings em CAND e INSTR serão todas relativamente pequenas (<50 caracteres) - ou seja, a string de destino INSTR NÃO é longa em relação às strings candidatas.
Atualizar Eu deveria ter mencionado, o conjunto de seqüências de caracteres CAND é invariável em todos os valores de INSTR.
Atualizar Eu só preciso saber que houve uma partida - e não preciso saber qual era a partida.
Atualização final Eu optei por tentar AhoCorsick e Rabin-Karp, devido à simplicidade de implementação. Como tenho padrões de comprimento variável, usei um Rabin-Karp modificado que hashes os primeiros n caracteres de cada padrão, onde n é o comprimento do menor padrão, N era, então, o comprimento da janela de pesquisa de substring rolante. Para o Aho Corsick eu useiisto
No meu teste eu procurei por 1000 padrões em dois artigos de artigos de notícias, média de 1000 iterações, etc ... Os tempos normalizados para completar foram:
AhoCorsick: 1
RabinKarp: 1,8
Pesquisa ingênua (marque cada padrão e use string.contains): 50
* Alguns recursos descrevendo os algos mencionados nas respostas abaixo:
http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module5/module5.html
http://www.cs.princeton.edu/courses/archive/spr09/cos226/lectures/18SubstringSearch-2x2.pdf