On 08.04.2012 22:49, Dmitry Olshansky wrote:
The refinement is merging prefixes and suffixes of course. And for that one needs to calculate hashes for all of prefixes and all of suffixes. I will define _all_ later on. First observation is that if you calculated partial checksums for prefixes you have sums for all suffixes and vise-versa. Namely: //prefix ends on i, suffix start on i sum_prefix[i] = total - sum_suffix[i]; that is derived from the fact that: total = sum_prefix[i] + sum_suffix[i]; (taking into account the properties of +/- in the finite field)
Mm btw there is one step from here to use it on arbitrary common slices (i, j) where i < j:
slice_sum(i, j) = sum_prefix[j] - sum_prefix[i] P.S. (Goes for walk citing a dynamic programming maxim) -- Dmitry Olshansky
