[learning notes] border and period

Actually, it's just copying blogs

Weak periodic theorem

$1.1$ if $p$ and $q$ yes $s$ The cycle of ,$p+q\le |s|$, be $\gcd (p,q)$ Also for the $s$ The cycle of

prove ：
Might as well set $p<q$, remember $d=q-p$
because $p+q\le |s|$, about $\forall i\in [1,|s|-d],i-p\ge 1\vee i+q\le n$
If the former holds ,$s_i=s_{i-p}=s_{i-p+q}=s_{i+d}$
If the latter is established ,$s_i=s_{i+q}=s_{i+q-p}=s_{i+d}$
so $d$ by $s$ The cycle of
Obviously, you can finally get $\gcd (p,q)$ yes $s$ The cycle of

border Structure

$1.2$ if $2|S|\ge |T|$, be $S$ stay $T$ The matching position in must be an arithmetic sequence .

prove ：
First the $T$ It's not being $S$ Remove the covered part
Consider matching as greater than $2$ The situation of
set up $S$ stay $T$ The first and second matching bit difference in is $d$, The bit difference between the second match and a later match is $q$, that $d,q$ Are all $S$ The cycle of , also $d+q\le |S|$, According to the weak periodic theorem $r=\gcd (d,q)$ yes $S$ The cycle of , set up $S$ The minimum period of is $p$, that $p|r$（ Otherwise you can use WPL Construct smaller cycles ）. here $p|r|d$.

if $p<d$, because $p$ yes $S$ The cycle of , Therefore, a matching bit closer to the first matching bit can be found , And $d$ The definition of contradiction

Therefore, it is only possible $p=r=d$, also $d|q$, So the matching bit is after processing $T$ On , Every time $d$ once , The matching position means that the tolerance is $d$ The arithmetic sequence of .

$1.3$ character string $s$ All not less than $\frac{|s|}{2}$ Of $\text{border}$ Form an arithmetic sequence

set up $s$ maximal $\text{border}$ by $n-p(p\le \frac{|s|}{2})$, the other one $\text{border}$ by $n-q(q\le \frac{|s|}{2})$
because $p$,$q$ yes $s$ The cycle of , therefore $\gcd (p,q)$ yes $s$ The cycle of
therefore $n-\gcd (p,q)$ yes $s$ Of $\text{border}$
therefore $p|q$
Again because $p$ yes $s$ The cycle of , therefore $s$ Your appearance can be painted
so $s$ All not less than $\frac{|s|}{2}$ Of $\text{border}$ Form an arithmetic sequence , The tolerance is $p$

$1.4$ inference ： character string $s$ All of the $\text{border}$ It can be divided into $O(\log |s|)$ paragraph , Each segment is an arithmetic sequence

take $s$ Of $\text{border}$ on length $x$ Divide into $\log |s|$ class , remember $2^k$ Is no more than $n$ Of $2$ Power of power
$x\in [1,2),[2,4),...,[2^{k-1},2^k),[2^k,n)$
about $x\in [2^k,n)$, obviously $2^k\ge \frac{n}{2}$, Then this segment forms an arithmetic sequence
about $x\in [2^{i-1},2^i)$, Consider a clever structure
Let's go straight to the map You should understand 233

The two tolerances are d1,d2 The tolerance should be lcm(d1,d2) Well

Then you can cut it off Mivik The title of the 了 .