Wrong lemma in two_way_notes.txt
Open
Nobody has claimed this yet.
docs
- Dominant language
- Python
- Stars
- 77.2k
- Forks
- 35.9k
- PR merge metrics
- PR metrics pending
Description
Hi @sweeneyde @tim-one
I think there is a wrong claim in the notes about two-way algorithm.
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).
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Read Objects/stringlib/stringlib_find_two_way_notes.txt around lines 352-353 and compare the stated lemma with the counterexample in the issue. Check the surrounding discussion of periods in the two-way algorithm notes, then revise the incorrect claim and verify that the example is handled consistently.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- documentation
- Issue type
- Documentation
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 45/100