Knuth–Morris–Pratt algorithm
en.wikipedia.org
Knuth–Morris–Pratt algorithm
1–10 of 50 posts
Re: Knuth–Morris–Pratt algorithm
#2I'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. :-)
Re: Knuth–Morris–Pratt algorithm
#3I'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…
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.
Re: Knuth–Morris–Pratt algorithm
#4KMP 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?
Re: Knuth–Morris–Pratt algorithm
#5KMP 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_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).
Re: Knuth–Morris–Pratt algorithm
#6KMP 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?
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.
Re: Knuth–Morris–Pratt algorithm
#7KMP 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?
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).
Re: Knuth–Morris–Pratt algorithm
#8I'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…
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.
I love to be surprised like that in interviews, let me tell you. Makes my decision much easier.
Re: Knuth–Morris–Pratt algorithm
#9KMP 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?
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 executed ;-)
So in theory KMP is faster, in practice for not very large strings I am really not sure... There are plenty of optimal algorithms where the fixed cost is too high for majority of useful cases comparing to less optimal algorithms with very low fixed costs. Does KMP have as much "mechanical sympathy" to overcome specific machine code instructions for most frequent cases?
Re: Knuth–Morris–Pratt algorithm
#10KMP 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_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 fo…
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.