It is straightfordward, you must precalculate the partial sums of the text,in each column... I am not sure if i remember correctl what is Rabin-Karp doing, but if sum is just a sum of ascii values, modulo some prime, for that case it works without problem.
2009/3/21, Miroslav Balaz <gpsla...@googlemail.com>: > 2009/3/21, sinan <sinanba...@gmail.com>: >> >> Hi, >> >> I'm studying on this subject recently. Now I've implemented a java >> code which can consume two 2darrays which are a Text(nXn) array and a >> Pattern(mXm). >> >> For now, it translates the pattern to a number which is the sum of the >> numbers in the pattern, and looks for the corresponding value in the >> text array by translating each mXm in the text. if the values are >> equal then it looks for a naive match which is quite reasonable >> because collisions might occur. >> >> For Example >> >> Text >> 0 3 5 50 >> 40 3 2 60 >> 0 100 200 70 >> 0 50 40 80 >> >> Pattern >> 100 200 >> 50 40 >> >> So the result is (1,2) >> >> >> But i also need to do what Rabin-Karp Matcher actually does. The text >> and pattern are preprocessed and p=390 >> and t00 = 46. While calculating t01 i need to forget about the 0 and >> 40 and add up the 5 and 2 to make t01 = 13. What i'm saying is that >> not to calculate it from the begining but substract 0 and 40 from 46 >> and add 5 and 2 on it. >> >> Can smbdy help i couldnt get through this. >> >> >> >> >> >> >> > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
