Rolling hash, Rabin Karp, palindromes, rsync and others

Rolling hash, Rabin Karp, palindromes, rsync and others

Given a string of length n, count the number of palindromic substring of S. Solve better than O(n²).

Given a string of length n, find the longest substring that is repeated at least k times. Solve in O(n log n)

Given a bitmap, find out the largest square that's repeated in the bitmap.

Given a string S figure out if the string is periodic. (there is a p such that for any i we have that s[i] == s[i + p]) For example abcabcab is periodic with p = 3. O(n log n)

Given two equal length strings, figure out if one is a rotation of the other. O(n)

Given two polygons find out if they are similar polygons. O(n)

Given a string, find it's longest periodic prefix. O(n log n) For aaabaaabcde the answer is aaabaaab

Given a tree T with character labeled nodes and a given string P count how many downward paths match P. O(n)

http://blog.teamleadnet.com/2012/10/rabin-karp-rolling-hash-dynamic-sized.html
Read full article from Rolling hash, Rabin Karp, palindromes, rsync and others