Check if a keyword is in a string
java
Solution
You can use Boyer-Moore, which involves preprocessing the string, but you're not going to be able to beat a worst case of O(KN), where K is the sum of the lengths of the keywords, and N is the length of the string. Best case is of course sublinear, but you can't have a worst case sublinear runtime.
Note that the comparisons aren't free. It's not like you can compare two strings in O(1) to see if they're equal, you have to iterate through the characters. Hashing gets you to what you need to compare to in constant time, but doesn't help more than that since two different strings can have the same hash. That's not to say that hashing isn't good, it is, but it does not alter the worst case runtime complexity.
In the end, you need to compare the characters, and Boyer-Moore provides a very good way to do that. Of course if you're using some sort of hash based build, you may be able to rule out certain keywords in amortized constant time, but that doesn't change the fact that in the worst case (and many other cases), you're going to need to compare characters.
Also note that depending on what we assume about the data, and how we construct our indexing structure(s), it's possible to achieve a very good actual runtime. Just because the worst case complexity isn't sublinear doesn't mean that the actual runtime won't be really fast. There is no singleton simple or correct solution, the problem can be approached in myriad ways. There's never a quick and dirty answer to solve all of your problems when it comes to information retrieval.
Problem
I have a list of keywords and I want to be able to find if a string contains any of those keywords. Right now the solution I have takes O(n). Is there a quicker way of doing this search without looping through each keywords and doing a comparison/contains? i.e. Keywords = "cat", "hat", "mat", "bat", "fat", "sat", "rat", "pat", "foo bar", "foo-bar" String = "There is a cat in the box." The result of this is true because "cat" matches one of the words in the 'keywords' EDIT: I guess I wasn't as clear when I said O(n). I mean to say O(n) where n=number of keywords.