«Проще говоря, это длина наиболее длинного начала строки, являющегося также и ее концом. „
Мне кажется, это интуитивно понятное определение. Плюс табличка служит примером.

Можете привести вывод среднего времени работы наивного алгоритма?

Спасибо, удобная конструкция.

Это невнимательность. Убрал.

Интерес представляет именно вывод алгоритма и его разъяснение.