Crowdly

Додати до Chrome

Let S be a string of length n , and, using 1-based indexing, let r_k den...

✅ Перевірена відповідь на це питання доступна нижче. Наші рішення, перевірені спільнотою, допомагають краще зрозуміти матеріал.

Let S be a string of length n, and, using 1-based indexing, let r_k denote the value of r at iteration k of the Z-algorithm when run on S. Then the sequence $(r_1, r_2, \dots, r_n)$ (r_1, r_2, \dots, r_n) is always non-decreasing, with $r_{i-1} \le r_i \quad \forall\, 1 < i \le n$ r_{i-1} \le r_i \quad \forall\, 1 < i \le n, for any S.