StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You can use <a href="http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm" rel="nofollow">Boyer-Moore</a>, 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.</p> <p>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. </p> <p>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.</p> <p>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.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload