Wrong lemma in two_way_notes.txt

[hugopm]

Hi @sweeneyde @tim-one

I think there is a wrong claim in the notes about two-way algorithm.

cpython/Objects/stringlib/stringlib_find_two_way_notes.txt

Lines 352 to 353 in 255eb37

	If p is a substring of s and p has period r, then the period
	of s is either equal to r or greater than len(p).

Let s = (abcccd)^2 = abcccdabcccd and p = ccdabcc of length len(p) = 7 and period r = 5.

The period of the whole string s is 6, which is strictly greater than r but strictly smaller than len(p).

[picnixz]

I've had a look at the lemma and, unless I'm mistaken, this is indeed a counterexample. I'm not entirely sure about the definition of a "period" in this case. Is this the period of ccdabcc itself as a substring in s or is it the period of p as a string itself?

I think I should have a look at the CFT but I don't have much time for that. Tim would be more familiar with this.