Re^4: Algorithm inspiration required. (Further thoughts on rolling checksums)

[vr]

NO intervening junk is the correct interpretation

What about presence or absence of preceding junk? If it's absent, i.e. sequence starts at 0, and if stream allows re-reading previous data, then read 2 bytes at 2N, look back at byte at N. Make N = N + 1 now. Update checksums for 0..(N-1) and N..(2N-1) halves (rolling hash). Byte read at "previous N" adds to checksum of half1, and deletes from checksum of half2. 2 bytes add to checksum for half2. Compare 2 checksums. And so on. Only 2 checksums stored at any time. I hope I didn't misunderstood the task to be too simple nor said anything too trivial.

[BrowserUk]

if stream allows re-reading previous data,

The definition of a stream is you cannot re-read it. I could store the stream to disk, but the cost of repeatedly re-reading large volumes of data is prohibitive.