I know it have been a long while that I do not update my website. Even missed the entire May…

Actually, I am confused about my future path during these two months. I got a bunch of offers from different places. However, I don’t even know where should I go ultimately.

So I just try to learn some new stuff as I can to kill the time…

Rabin-Karp is a kind of string searching algorithm which created by Richard M. Karp and Michael O. Rabin. It uses the rolling hash to find an exact match of pattern in a given text. Of course, it is also able to match for multiple patterns.

def search(pattern, text, mod): # Let d be the number of characters in the input set d = len(set(list(text))) # Length of pattern l_p = len(pattern) # Length of text l_t = len(text) p = 0 t = 0 h = 1 # Let us calculate the hash value of the pattern # hash value for pattern(p) = Σ(v * dm-1) mod 13 # = ((3 * 102) + (4 * 101) + (4 * 100)) mod 13 # = 344 mod 13 # = 6 for i in range(l_p - 1): h = (h * d) % mod # Calculate hash value for pattern and text for i in range(l_p): p = (d * p + ord(pattern[i])) % mod t = (d * t + ord(text[i])) % mod # Find the match for i in range(l_t - l_p + 1): if p == t: for j in range(l_p): if text[i+j] != pattern[j]: break j += 1 if j == l_p: print("Pattern is found at position: " + str(i+1)) if i < l_t - l_p: t = (d*(t-ord(text[i])*h) + ord(text[i+l_p])) % mod if t < 0: t += mod text = "ABCCCDCCDDAEFG" pattern = "CDD" search(pattern, text, 13)