Written before

Border Theory,which was not well-known enough,should have been publicized together with KMP or similar algorithms.But nowadays lots of people don't know such a theory exist,making them unable to solve several tasks easily or even can't get a fast solution.So it's time to complete the blog as what I will do on this.

Conclution

For a string $$$S$$$, There are a squence of strings:

it's garenteed that there exist a way to divide the sequence into $$$\operatorname{O}(\log |S|)$$$ continuous subsequence that each subsequence forms an arithmetic sequence.

Proof

First of all,we found that if there's a string $$$T$$$ as a border of $$$S$$$ and $$$2|T| \ge |S|$$$, Then the sequence of where $$$T$$$ appears in $$$S$$$ forms an arthmetic sequence.

Second,We found that all lengths of border $$$T$$$ that $$$2|T| \ge |S|$$$ will form an arthmetic sequence:

So there's a way that if $$$p \lt q,p,q \text{are the length of borders}$$$ not in the same continuous sequence, $$$2p \lt q$$$ exist,So the conclution is right.