print "match"
==

h2. Substrings of variable length
 
The polynomial function can be used to compute hashes for substrings of varying length
 
Let’s choose <tex>H(S[i..j]) = S[i]+S[i+1]a+S[i+2]a{2}+...+S[j]a^{j-i} </tex> Then we compute the array h which contains cummulative hashes: <tex>h[k]=S[0]+S[1]a+S[2]a^{2}+...+S[k]a^{k}</tex>. It’s easy to see that <tex>H(S[i..j])=(h[j]-h[i-1])/a^i</tex>
 

h2. Longest common substring
bq. Given three strings, compute their longest common substring.

bq. Given a string of length n, find out it's largest palindromic subsequence.

The naive solution is O(n^3). For every possible subsequence it tests in linear time if it's a palindrome.

The naive solution is O(n^3^). For every possible subsequence it tests in linear time if it's a palindrome.

A smarter solution tries every position in the original string as the center of a palindrome and extends to the left and to the right as long as the ... This solution takes O(n^2) time.

A smarter solution tries every position in the original string as the center of a palindrome and extends to the left and to the right as long as the corresponding characters match. This solution takes O(n^2^) time.

There's a O(n log n) solution that involves rolling hash. For a fixed length ... then we do a binary search.

There's a O(n log n) solution that involves rolling hash. Given X we can test if there is any substring S' of S of length 2X such that H(S') == H(reverse(S')). The identity means that S contains a palindromic sequence of length at least 2X. What is left is to find out the maximum X for which we can find a S' such that the equality holds. We can use binary search to do that efficiently. The overall complexity is O(n log n).
 
h2. Substrings of variable length
 
The polynomial function can be used to compute hashes for substrings of varying length
 
Let’s choose <tex>H(S[i..j]) = S[i]+S[i+1]a+S[i+2]a{2}+...+S[j]a^{j-i} </tex> Then we compute the array h which contains cummulative hashes: <tex>h[k]=S[0]+S[1]a+S[2]a^{2}+...+S[k]a^{k}</tex>. It’s easy to see that <tex>H(S[i..j])=(h[j]-h[i-1])/a^i</tex>

h2. Caveats