Why do we multiply each eleemnt with pow(prime,i)…basically i am not undersatnding the reason to why add this extra,why cannot we directly just sum up the ascii values?
Rabin karp rolling hash function
we do it so that hash function gives unique value each time.
Say ascii value is 4 and 2 then we can do 4+2=6
Now, 6 can be from 5+1 as well so we will have a lot of collison.
In power,we will have 4prime^i+prime2
its more or less like we write 42 as 4*10+2 so, we can get 4 and 2.
We will need to update hash function in O(1) time so we will need a way to get the first digit in O(1) time hence we don’t just add naturally