Editing Rabin–Karp algorithm
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 22: | Line 22: | ||
One of the simplest rolling hashes is given by <math>H(a_0, a_1, \ldots, a_p) = a_0 + a_1 x + a_2 x^2 + \ldots + a_p x^p</math>, where <math>x</math> is fixed and the polynomial evaluation is taken modulo a small, fixed base, usually the size of the machine word (which is a power of two), for the sake of efficiency. (To use this, we assign a non-negative integer to each character in the alphabet; often we simply use the ASCII code.) To see why this is useful, consider: | One of the simplest rolling hashes is given by <math>H(a_0, a_1, \ldots, a_p) = a_0 + a_1 x + a_2 x^2 + \ldots + a_p x^p</math>, where <math>x</math> is fixed and the polynomial evaluation is taken modulo a small, fixed base, usually the size of the machine word (which is a power of two), for the sake of efficiency. (To use this, we assign a non-negative integer to each character in the alphabet; often we simply use the ASCII code.) To see why this is useful, consider: | ||
:<math>H_i = H(T_{i+1}, \ldots, T_{i+m}) = T_{i+1} + T_{i+2}x + \ldots + T_{i+m-1} x^{m-2} + T_{i+m}x^{m-1}</math> | :<math>H_i = H(T_{i+1}, \ldots, T_{i+m}) = T_{i+1} + T_{i+2}x + \ldots + T_{i+m-1} x^{m-2} + T_{i+m}x^{m-1}</math> | ||
− | :<math>H_{i+1} = H(T_{i+2}, \ldots, T_{i+m+1}) = T_{i+2} + T_{i+3}x + \ldots + T_{i+m} x^{m- | + | :<math>H_{i+1} = H(T_{i+2}, \ldots, T_{i+m+1}) = T_{i+2} + T_{i+3}x + \ldots + T_{i+m} x^{m-1} + T_{i+m+1}x^{m-1}</math> |
How can we compute <math>H_{i+1}</math> given <math>H_i</math> and the text <math>T</math>? Looking closely, it becomes clear that <math>H_{i+1} = \frac{H_i-T_{i+1}}{x} + T_{i+m+1} x^{m-1}</math>. | How can we compute <math>H_{i+1}</math> given <math>H_i</math> and the text <math>T</math>? Looking closely, it becomes clear that <math>H_{i+1} = \frac{H_i-T_{i+1}}{x} + T_{i+m+1} x^{m-1}</math>. | ||