hadi's blog

By hadi, 9 years ago, In English,
Sometimes you face a string processing problem for which you have the correct idea, but implementing it might not be so easy. In some of these cases, you can find a much easier to implement algorithm using hashing. These algorithms don't always give correct answer, but their probability of giving wrong answer is very low.

 The simplest example is string matching, where you have to find a string inside another string. Well, you can use the KMP algorithm, which is fast enough, and easy to implement if you have enough practice. There's an alternative using hashing: Rabin-Karp algorithm. You probably should know it so you can invent more powerful algorithms for more difficult problems.

 The above example might not show you the high power of the hashing. But problems aren't that simple most of the time:
  • Matrix Matcher: There are alternative methods for solving this problem too, e.g. using the Aho-Corasick algorithm. But the solution using hashing is much easier to implement, once you know how to use hashing. See UVa OJ board for more information.
  • Compressed String: Implementing hash solution isn't as easy as the previous cases, but it's idea is easy. In fact, I don't know any other good solution for this problem. To be more accurate, you can use Binary Search + Hashing to solve this problem, and to be more accurate you can use multiple hash bases. Thanks to rem and gmark for telling me that hashing works here.

You see, hashing is a good thing :-) But probably not always. You should always do some math to calculate how likely is your solution to pass. For example, it might be hard to find a hashing algorithm which passes all test cases of "Lost in Translation". It's not so hard to see why.
 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it