1
$\begingroup$

We're given a fixed text, and we are presented with a series of online queries of patterns. For each query, the goal is to answer if the pattern exists in the text. Each pattern is a string, and we want to know if it appears as a substring of the text. The text can be preprocessed.

What's the optimal way to solve this?

$\endgroup$
  • $\begingroup$ I'm not an expert, but I'd look at the algorithms based on suffix arrays. $\endgroup$ – chi Jan 9 '16 at 13:22
4
$\begingroup$

By building a suffix trie.

If you wish to preprocess the search query, then there is this algorithm by Boyer–Moore, whose complexity is believed to be linear after applying Galil Rule (details in the same page).

Other than that, if you can preprocess the whole text before hand and construct a Suffix Trie, then you can achieve many things. But the main limitation is it requires a lot of space.

See Suffix Trees and the lecture from MIT (Complete List)

See also Popular String searching algorithms.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.