Всем известно, что если посадить обезьяну за печатную машинку и заставить ее вечно случайно стучать по клавишам, то, рано или поздно, она напечатает «Войну и мир», собрание трудов Пифагора и даже статью, которую вы сейчас читаете.

![][1]

Потрясающий факт, но еще интереснее попытаться понять, сколько же времени ей понадобится для набора конкретного текста. А вам очевидно, что строку «abc» набирать гораздо быстрее чем «aaa»? Решению этой задачи и посвящен этот пост. Попутно объясняется префикс функция и ее свойства.

[Читать дальше →][2]

[1]: https://habrastorage.org/files/e15/7d9/8f5/e157d98f57474214886b657bdfa2a17f.jpg
[2]: https://habrahabr.ru/post/200834/#habracut