Imagine the repeat sequence we are trying to detect is:

    Abcdeabcdefabcdefg
[download]

So the input stream will look something like:

    ...AbcdeabcdefabcdefgAbcdeabcdefabcdefgAbcdeabcdefabcdefg...
[download]

but we may start sampling at any point. eg.

    deabcdefabcdefgAbcdeabcdefabcdefgAbcdeabcdefabcdefgAbcdeabcdefabcd
+efgAbcdeabcdefabcdefgAbcdeabcdefabcdefg
    1              2  3              4  5              6
[download]

• We won't see the start of a full sequence repeat until 2, but we won't have enough information to know that.
• We will have seen a full-but-disjoint sequence at 3, but will not have enough information to know that.
• We will have seen a full repeat -- start to end -- and point 4, but probably won't have enough info to know that?
• At point 5 we will have seen two, full-but-disjoint repeats; we should be able to detect this?
• At point 6 we will have seen two full, complete repeats and we should definitely be able to detect this.

If we maintain rolling checksums, then:

• At point 3 we will have a checksum for a full-but-disjoint sequence, but will not be able to match it until point 5.
• At point 4 we will have a checksum for a full sequence, but will not be able to match it until point 6.

But this would require us to store checksums covering every start-point and every end-point, for 2 full-but-disjoint repeats. That's N^2 checksums, which is more expensive than storing the data.

Unless there is some way to determine that we can discard those checksums that cannot be the one we want.

Ie. If when we read the 3rd value, and calculate the 2-value checksum for that value and its immediate predecessor and it doesn't match the checksum for the first two values, we know that our sequence must be longer than 2, and can discard both 2-value checksums.

Ditto, when we read the fourth value, and calculate the checksum for the last 3 values and it does not match that of the first 3, we can discard both.

But, when we calculated the 3-value checksum having read the fourth value, we needed the 2-value checksums; and when we come to calculate the 4-value checksums having read the 5 value, we need the 3-value checksums;

So the discarding of earlier checksums has to be deferred by one iteration cycle.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.