8 ms·

Knuth–Morris–Pratt algorithm

117 points by rbcoffee 12y ago

Cieplak 12y ago
Here is the boost implementation: http://www.boost.org/doc/libs/1_55_0/libs/algorithm/doc/html/the_boost_algorithm_library/Searching/KnuthMorrisPratt.html http://www.boost.org/doc/libs/1_55_0/libs/algorithm/doc/html...
- Intermernet 12y ago
  Here's one in Go :-) http://play.golang.org/p/chYGT69vBc http://play.golang.org/p/chYGT69vBc
kevingadd 12y ago
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 optimize it. I said 'knuth morris pratt' and gave a basic overview of the algorithm and explained how it's faster. He insisted the algorithm couldn't possibly work. I spent a few more minutes trying to explain it, but I couldn't convince him. The dark magic of efficient string searches evades us all sometimes, I suppose. I always like coming away from an interview feeling like I learned something, so I hope he googled the algorithm later. :-)
- jiggy2011 12y ago
  That's the risk with interview questions, that the candidate suggests a better solution that the interviewer anticipated. Leaving the interviewer with the task of ascertaining whether the solution is correct.
  - foobarian 12y ago
    I love to be surprised like that in interviews, let me tell you. Makes my decision much easier.
    - noir_lord 12y ago
      > Makes my decision much easier. You didn't say which way, I've worked with and for people who wouldn't hire someone smarter than them, the human psyche is a dark place.
      - gedrap 12y ago
        That's true. On other hand, it's just for the interviewees own good - you don't want to work with people like that ;) except from megacorps with hundreds and thousands of devs
  - taeric 12y ago
    This story is borderline baffling, though. If you flat out named the algorithm and it contains a famous name like Knuth, that should be good enough to go. That you may not have all of the points of it memorized is irrelevant. Now, if you name a very obscurely named algorithm, that is one thing. But seriously, Knuth!? Is anyone involved with optimizations and serious algorithm design not aware of that name?
- mightybyte 12y ago
  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.
  - pedrocr 12y ago
    Wikipedia says Boyer Moore is O(n+m) which is the same as this algorithm. https://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm#Performance https://en.wikipedia.org/wiki/Boyer-Moore_string_search_algo...
    - mightybyte 12y ago
      That's worst case complexity. It's the average case where Boyer Moore wins over KMP.
- bitdiddle 12y ago
  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/030439759390239P http://www.sciencedirect.com/science/article/pii/03043975939...
bitL 12y ago
KMP is conceptually very cool, as well as other clever string searching algorithms (BM, RK, AC), though one of the questions for me always was if even its most efficient implementation wouldn't be always slower than executing a brute-force combination of REP CMPSL/CMPSB instructions (x86) for vast majority of searched strings?
- ekr 12y ago
  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.
  - alayne 12y ago
    O(m*n) is not the same as O(n^2).
    - rimantas 12y ago
      It's the same when m=n.
      - waps 12y ago
        Of course in string search it never is. In m=n case KMP would simply compare the first character, and if it doesn't match declare nothing was found. Yes there'd be much more different instructions involved but I think KMP would start beating naive pretty quickly in the m=n case.
      - deleted 12y ago
        [deleted]
    - xyzzyz 12y ago
      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).
mavam 12y ago
KMP starts with the first character of the pattern (or substring/needle) and then jumps forward by the length of the mismatch. A related algorithm is Boyer-Moore (BM)(http://en.wikipedia.org/wiki/Boyer–Moore_string_search_algorithm http://en.wikipedia.org/wiki/Boyer–Moore_string_search_algor...), which operates the other way round: it begins with the last character of the pattern and then compares backwards until the full pattern matches. The advantage of BM is that it allows for bigger jumps. It seems that KMP works well for small alphabets (e.g., DNA), whereas BM shines for larger alphabets (e.g., plain English).
- yxhuvud 12y ago
  One difference is that BM is O(m*n) while KMP is O(n + m). Depending on how the input string looks like, this can matter - especially in small alphabets where the likelihood of pattern repeating themselves are bigger.
  - IsTom 12y ago
    BM is too provably O(n + m) (and without dependence on alphabet size unlike KMP) if you apply two heurestics that I don't really remember. For some reason it's not mentioned on wikipedia.
    - jasode 12y ago
      Turbo BM? http://www-igm.univ-mlv.fr/~lecroq/string/node15.html http://www-igm.univ-mlv.fr/~lecroq/string/node15.html
volaski 12y ago
Why is KMP on the front page of HN? Not complaining, just confused. Is this related to some other news?
- DanBC 12y ago
  It's a weekend and other material surfaces.
  - devcpp 12y ago
    Yup welcome to the slow hours in the weekend on HN. Personally, I like the change.
- gedrap 12y ago
  Because it takes just a few votes (4-7 in first ~45min, from my experience) to bring something up to the front page. Plus a cool name, I guess.
- fengjingchao 12y ago
  Because people like you and me are bored enough to reply here..
- blencdr 12y ago
  reminds me that I implemented it 10 years ago... and forgot it in the meantime. It's nice to see a good old friend.
- freditup 12y ago
  I personally like this kind of submission. If it's something I was familiar with, then it's a good review/reminder; if it's something I was unfamiliar with, it's a good lesson.
- brudgers 12y ago
  Because it is of interest to hackers and rightly so. Some submittals are good because they are cutting edge, others because they touch on the fundamental - the magical - aspects of computing. In terms is it being news, it's a bit of a feature story rather than on the scene reporting of a city council meeting or a cub's coverage of the police blotter or the Chamber of Commerce recent press release wrapped up as news. If nothing else it's better than a blog post about the algorithm, and for me it's always helpful to be reminded what an amazing resource Wikipedia has become for computer science topics.
reledi 12y ago
A few months ago I stumbled on James Morris' GitHub profile [1] by accident. There's not much activity, but he has dabbled with Ruby on Rails. 1: https://github.com/jhm15217/ https://github.com/jhm15217/
deleted 12y ago
[deleted]
deckar01 12y ago
The FM-Index changed the way I think about searching. http://alexbowe.com/fm-index/ http://alexbowe.com/fm-index/
wslh 12y ago
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-streams-a-slight-modification-of-the-knuth-morris-pratt-algorithm-in-haxe/ http://blog.databigbang.com/searching-for-substrings-in-stre...
ladon86 12y ago
Here's an easy to follow video explaining the algorithm: https://www.youtube.com/watch?v=rfisBOOLN9M https://www.youtube.com/watch?v=rfisBOOLN9M
chaoxu 12y ago
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.hs https://github.com/Mgccl/haskell-algorithm/blob/master/KMP.h... Description: http://www.chaoxuprime.com/posts/2014-04-11-the-kmp-algorithm-in-haskell.html 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 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/AhoCorasick.hs https://github.com/Mgccl/haskell-algorithm/blob/master/AhoCo...
- platz 12y ago
  Looks like there's also a KMP implementation here specialized to ByteStrings: http://hackage.haskell.org/package/stringsearch http://hackage.haskell.org/package/stringsearch
kinow 12y ago
I learned about this algorithm recently, because of an exercise in the Rosalind bioinformatics problems list: http://rosalind.info/problems/kmp/ http://rosalind.info/problems/kmp/ There are tons of other interesting algorithms put in practice in different bioinformatics problems.

117 points by rbcoffee 12y ago

Here is the boost implementation: http://www.boost.org/doc/libs/1_55_0/libs/algorithm/doc/html/the_boost_algorithm_library/Searching/KnuthMorrisPratt.html http://www.boost.org/doc/libs/1_55_0/libs/algorithm/doc/html...

Intermernet 12y ago
Here's one in Go :-) http://play.golang.org/p/chYGT69vBc http://play.golang.org/p/chYGT69vBc

kevingadd 12y ago

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 optimize it. I said 'knuth morris pratt' and gave a basic overview of the algorithm and explained how it's faster. He insisted the algorithm couldn't possibly work. I spent a few more minutes trying to explain it, but I couldn't convince him. The dark magic of efficient string searches evades us all sometimes, I suppose. I always like coming away from an interview feeling like I learned something, so I hope he googled the algorithm later. :-)

jiggy2011 12y ago
That's the risk with interview questions, that the candidate suggests a better solution that the interviewer anticipated. Leaving the interviewer with the task of ascertaining whether the solution is correct.
- foobarian 12y ago
  I love to be surprised like that in interviews, let me tell you. Makes my decision much easier.
  - noir_lord 12y ago
    > Makes my decision much easier. You didn't say which way, I've worked with and for people who wouldn't hire someone smarter than them, the human psyche is a dark place.
    - gedrap 12y ago
      That's true. On other hand, it's just for the interviewees own good - you don't want to work with people like that ;) except from megacorps with hundreds and thousands of devs
- taeric 12y ago
  This story is borderline baffling, though. If you flat out named the algorithm and it contains a famous name like Knuth, that should be good enough to go. That you may not have all of the points of it memorized is irrelevant. Now, if you name a very obscurely named algorithm, that is one thing. But seriously, Knuth!? Is anyone involved with optimizations and serious algorithm design not aware of that name?
mightybyte 12y ago
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.
- pedrocr 12y ago
  Wikipedia says Boyer Moore is O(n+m) which is the same as this algorithm. https://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm#Performance https://en.wikipedia.org/wiki/Boyer-Moore_string_search_algo...
  - mightybyte 12y ago
    That's worst case complexity. It's the average case where Boyer Moore wins over KMP.
bitdiddle 12y ago
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/030439759390239P http://www.sciencedirect.com/science/article/pii/03043975939...

bitL 12y ago

KMP is conceptually very cool, as well as other clever string searching algorithms (BM, RK, AC), though one of the questions for me always was if even its most efficient implementation wouldn't be always slower than executing a brute-force combination of REP CMPSL/CMPSB instructions (x86) for vast majority of searched strings?

ekr 12y ago
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.
- alayne 12y ago
  O(m*n) is not the same as O(n^2).
  - rimantas 12y ago
    It's the same when m=n.
    - waps 12y ago
      Of course in string search it never is. In m=n case KMP would simply compare the first character, and if it doesn't match declare nothing was found. Yes there'd be much more different instructions involved but I think KMP would start beating naive pretty quickly in the m=n case.
    - deleted 12y ago
      [deleted]
  - xyzzyz 12y ago
    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).

mavam 12y ago

KMP starts with the first character of the pattern (or substring/needle) and then jumps forward by the length of the mismatch. A related algorithm is Boyer-Moore (BM)(http://en.wikipedia.org/wiki/Boyer–Moore_string_search_algorithm http://en.wikipedia.org/wiki/Boyer–Moore_string_search_algor...), which operates the other way round: it begins with the last character of the pattern and then compares backwards until the full pattern matches. The advantage of BM is that it allows for bigger jumps. It seems that KMP works well for small alphabets (e.g., DNA), whereas BM shines for larger alphabets (e.g., plain English).

yxhuvud 12y ago
One difference is that BM is O(m*n) while KMP is O(n + m). Depending on how the input string looks like, this can matter - especially in small alphabets where the likelihood of pattern repeating themselves are bigger.
- IsTom 12y ago
  BM is too provably O(n + m) (and without dependence on alphabet size unlike KMP) if you apply two heurestics that I don't really remember. For some reason it's not mentioned on wikipedia.
  - jasode 12y ago
    Turbo BM? http://www-igm.univ-mlv.fr/~lecroq/string/node15.html http://www-igm.univ-mlv.fr/~lecroq/string/node15.html

volaski 12y ago

Why is KMP on the front page of HN? Not complaining, just confused. Is this related to some other news?

DanBC 12y ago
It's a weekend and other material surfaces.
- devcpp 12y ago
  Yup welcome to the slow hours in the weekend on HN. Personally, I like the change.
gedrap 12y ago
Because it takes just a few votes (4-7 in first ~45min, from my experience) to bring something up to the front page. Plus a cool name, I guess.
fengjingchao 12y ago
Because people like you and me are bored enough to reply here..
blencdr 12y ago
reminds me that I implemented it 10 years ago... and forgot it in the meantime. It's nice to see a good old friend.
freditup 12y ago
I personally like this kind of submission. If it's something I was familiar with, then it's a good review/reminder; if it's something I was unfamiliar with, it's a good lesson.
brudgers 12y ago
Because it is of interest to hackers and rightly so. Some submittals are good because they are cutting edge, others because they touch on the fundamental - the magical - aspects of computing. In terms is it being news, it's a bit of a feature story rather than on the scene reporting of a city council meeting or a cub's coverage of the police blotter or the Chamber of Commerce recent press release wrapped up as news. If nothing else it's better than a blog post about the algorithm, and for me it's always helpful to be reminded what an amazing resource Wikipedia has become for computer science topics.

reledi 12y ago

A few months ago I stumbled on James Morris' GitHub profile [1] by accident. There's not much activity, but he has dabbled with Ruby on Rails. 1: https://github.com/jhm15217/ https://github.com/jhm15217/

deleted 12y ago

[deleted]

deckar01 12y ago

The FM-Index changed the way I think about searching. http://alexbowe.com/fm-index/ http://alexbowe.com/fm-index/

wslh 12y ago

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-streams-a-slight-modification-of-the-knuth-morris-pratt-algorithm-in-haxe/ http://blog.databigbang.com/searching-for-substrings-in-stre...

ladon86 12y ago

Here's an easy to follow video explaining the algorithm: https://www.youtube.com/watch?v=rfisBOOLN9M https://www.youtube.com/watch?v=rfisBOOLN9M

chaoxu 12y ago

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.hs https://github.com/Mgccl/haskell-algorithm/blob/master/KMP.h... Description: http://www.chaoxuprime.com/posts/2014-04-11-the-kmp-algorithm-in-haskell.html 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 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/AhoCorasick.hs https://github.com/Mgccl/haskell-algorithm/blob/master/AhoCo...

platz 12y ago
Looks like there's also a KMP implementation here specialized to ByteStrings: http://hackage.haskell.org/package/stringsearch http://hackage.haskell.org/package/stringsearch

kinow 12y ago

I learned about this algorithm recently, because of an exercise in the Rosalind bioinformatics problems list: http://rosalind.info/problems/kmp/ http://rosalind.info/problems/kmp/ There are tons of other interesting algorithms put in practice in different bioinformatics problems.