Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
