Fast algorithm for searching for substrings in a string

Question

I'd like an efficient algorithm (or library) that I can use in Java to search for substrings in a string. What I would like to do is: Given an input string - INSTR: "BCDEFGH" And a set of candidate strings - CAND: "AB", "CDE", "FG", "H", "IJ" Find any CAND strings that match as substrings within INSTR In this example I would match "CDE", "FG", and "H" (but not "AB" and "IJ") There could be many thousand candidate strings (in CAND), but more importantly I will be doing this search many millions of times so I need it to be FAST. I'd like to work with char arrays. Also, I'm not intested in architectural solutions, like distributing the search - just the most efficient function/algorithm for doing it locally. Additionally, all the strings in CAND and INSTR will all be relatively small (< 50 chars) - i.e. the target string INSTR is NOT long relative to the candidate strings. Update I should have mentioned, the set of CAND strings is invariant across all values of INSTR. Update I only need…

Accepted Answer

Read up on the Aho-Corasick algorithm and the Rabin-Karp algorithm.

If the input is not too large, you don't want to repeat the search many times and you do not have many patterns, it might be a good idea to use a single pattern algorithm several times. The Wikipedia article on search algorithms gives many algorithms with running and preprocessing times.

Implementations:

- https://hkn.eecs.berkeley.edu/~dyoo/java/index.html

- http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html

- https://github.com/hankcs/AhoCorasickDoubleArrayTrie

- https://github.com/RokLenarcic/AhoCorasick

- https://github.com/robert-bor/aho-corasick

Presentations:

- http://www.slideshare.net/taka111/ahocorasick-string-matching-algorithm-15078438

Fast algorithm for searching for substrings in a string

Solution

Problem