1632
правки
Изменения
м
rollbackEdits.php mass rollback
=== Упрощенный алгоритм ===
Прежде чем перейти к объяснению алгоритма Крочемора, вначале опишем простой алгоритм, который на каждом этапе достигает такого же результата, что и алгоритм Крочемора, а именно: в строке <tex> S </tex> он вычисляет все повторяющиеся подстроки длиной <tex> l </tex>, где <tex> l = 1,2,...,n - 1</tex>.
Рассмотрим следующую строку Фиббоначи:
|| ||<tex> 1</tex> || <tex> 2</tex> || <tex> 3</tex> || <tex> 4</tex> || <tex> 5</tex> || <tex> 6 </tex>|| <tex> 7</tex> ||<tex> 8</tex> ||<tex> 9 </tex>|| <tex> 10 </tex>|| <tex> 11 </tex>|| <tex> 12</tex> || <tex> 13 </tex>|| <tex> 14 </tex>
|-
|<tex>f_6 = </tex> || a || b || a || a || b || a || b || a || a || b || a || a || b || $
|}
== Псевдокод ==
'''function''' crochemore(s: '''string'''): '''string'''
<tex>l</tex> <tex>\gets</tex> 1
Вычислим все последовательности на уровне 1 и пометим их как малые
