资 源 简 介
This implementation allows the detection, in quasi-linear time, of all the maximal repeats in one, or more, strings.
Let S a string of lenght ""n"" over a finite alphabet Σ.
Si refer to the i-th character of S.
Si..j refers to a substring of S starting at the position i and ending at position j.
Each position 0 ≤ i < n represents a unique suffix Si..n-1 of S.
LCi refers to the Left Context of a suffix i. We note £ the special left context LC0.
We note with the special symbol $ the character Sn.
A triple (p1 , p2 , l) is called repeat in S iff :
1. (p1+l-1 < n) ∧ (p2+l-1 < n) ∧ p1 ≠ p2
1. Sp1..(p2+l-1) = Sp2..(p2+l-1)
A repeat is called Left Maximal if LCp1 ≠ LCp1 ∨ LCp1 = £ ;
