String Searching Algorithm: Rabin-Karp | Ricardo Castro
There are always those situations, when all of us are faced with the problem of finding a substring inside a string, or string in a text, or a set of pattern strings on a text (whatever flavour you like). Being this a common "problem" chances are your language of choice already has a very good implementation that you can use.
But, it might be the case, that you really have to implement it yourself or you just want to understand how such a thing might work. There are several alternatives such as Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm, Rabin-Karp algorithm, just to name a few. The first two are probably more "famous" and so we will focus on the third one. We'll find out how it works because, although it has a slower worst case scenario, it's the algorithm of choice when we need multi-pattern search.
Let's think about a simple, naive solution. What we could do is go through our string comparing our substring, incrementing the initial comparisson position as we go, until we either found a match our we reached the end.
Read full article from String Searching Algorithm: Rabin-Karp | Ricardo Castro
No comments:
Post a Comment