Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Knuth–Morris–Pratt algorithm

en.wikipedia.org

Post reply on HN
Print view View original

31–40 of 50 posts

Re: Knuth–Morris–Pratt algorithm

#31

Post by bitdiddle »

kevingadd wrote: post #2

I've always liked the elegance of this algorithm, fun little example of how you can make things incredibly fast by thinking about your problem. And a related anecdote: I was interviewing at Apple for a systems development related role (graphics drivers, I think?) and one of the senior-level folks asked me to write strstr on the whiteboard. I started with a naive, working implementation, then he asked me how I'd optim…

There's some interesting theoretical work that was done by Srinivas in the 90s[1], that takes a geometric view of pattern matching, based on sheaves, and uses it to derive a generalized version of KMP that can be applied in other domains. I'm not sure what happened to this research program, and forget most of the details, but I heard a talk by Srinivas and recall thinking it was a very practical and real application of category theory.

[1] http://www.sciencedirect.com/science/article/pii/03043975939...

Re: Knuth–Morris–Pratt algorithm

#33

Post by xyzzyz »

alayne wrote: post #7
ekr wrote: post #6

Earlier quoted context omitted.

The time complexity of KMP is O(n), while the complexity of your idea is O(n^2). Considering the fact that KMP is not even doing a lot of things in its inner loop, (few memory accesses), a rep cmpsb approach is really no match for it, even in the trivial cases. So no, it's much faster.

O(m*n) is not the same as O(n^2).

Yes, but if something is O(m*n) and m <= n (which is the case in string search), then it's also O(n^2). On the other hand, since m can be of the order of, say, n/2, it's not too confusing to say that naive string search is O(n^2), since it's actually Theta(n^2).

Re: Knuth–Morris–Pratt algorithm

#35

Post by pedrocr »

mightybyte wrote: post #25
kevingadd wrote: post #2

I've always liked the elegance of this algorithm, fun little example of how you can make things incredibly fast by thinking about your problem. And a related anecdote: I was interviewing at Apple for a systems development related role (graphics drivers, I think?) and one of the senior-level folks asked me to write strstr on the whiteboard. I started with a naive, working implementation, then he asked me how I'd optim…

IMO the Boyer-Moore string searching algorithm is way more elegant. Average case performance of O(n/m)?!? That means that the longer the string you're searching for the faster you can find it! It obviously makes perfect logical sense once you think about it, but when I first heard about the algorithm it seemed magical.

Wikipedia says Boyer Moore is O(n+m) which is the same as this algorithm.

https://en.wikipedia.org/wiki/Boyer-Moore_string_search_algo...

Re: Knuth–Morris–Pratt algorithm

#36

Post by mtdewcmu »

bitL wrote: post #9
ekr wrote: post #6

Earlier quoted context omitted.

The time complexity of KMP is O(n), while the complexity of your idea is O(n^2). Considering the fact that KMP is not even doing a lot of things in its inner loop, (few memory accesses), a rep cmpsb approach is really no match for it, even in the trivial cases. So no, it's much faster.

I know about the time complexity, but my argument points to the CPU architecture and cache/branch prediction efficiency. KMP has a lot of branching which is more expensive than a simple cache (line) hit, cache REP CMPSx doesn't have any branching, aborts immediately after a mismatch with only a single loop over the starting position, search is also pretty much linear. This is not a Turing machine where it is being ex…

You're asking a question that the experts have also asked, so it's definitely a good question. The algorithm you're talking about is also called the naive algorithm. It's much faster in practice than you might expect given its simplicity and poor worst-case performance. That's because pathological behavior doesn't actually happen that often, and most of the time it is quite efficient.

I'm not sure whether it or KMP would be faster. But it doesn't matter much in the real world, because even better algorithms, like Boyer-Moore and its derivatives are faster still, and they are used instead.

Re: Knuth–Morris–Pratt algorithm

#37

Post by wslh »

I always wondered why most common KMP and RE implementations don't take into account the case of using streams instead of strings. That's why I ended up writing this article (with code) "Searching for Substrings in Streams: a Slight Modification of the Knuth-Morris-Pratt Algorithm in Haxe" [1] and adding information about a currently unsupported RE lib that take into account streams.

Hope this helps.

[1] http://blog.databigbang.com/searching-for-substrings-in-stre...

Re: Knuth–Morris–Pratt algorithm

#39

Post by chaoxu »

I have implemented KMP in Haskell. This version doesn't use any index! It is built purely functionally by realizing KMP's failure table is just a finite state automaton(well, almost...) However it is much longer than the C++ version...

Code: https://github.com/Mgccl/haskell-algorithm/blob/master/KMP.h... Description: http://www.chaoxuprime.com/posts/2014-04-11-the-kmp-algorith...

Actually, KMP is a little harder to program purely functionally than the MP algorithm. An extremely elegant MP algorithm is implemented here: http://twanvl.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell (Note it says the algorithm is KMP, but it is actually the MP algorithm).

The Aho–Corasick string matching algorithm is a generalization of the MP algorithm. Which I also coded in Haskell inspired by the MP code above. https://github.com/Mgccl/haskell-algorithm/blob/master/AhoCo...

Post reply on HN