}
*'''Корректность работы'''
[[Файл:Prefix1.jpg|center]] Как видно из рисунка, при совпадении символов <tex>S[k]</tex> и <tex>S[i]</tex> длина наибольшего общего префикса увеличивается на 1. В случае, когда символы <tex>S[k]</tex> и <tex>S[i]</tex> не совпадают, <tex>pi(k-1)</tex> - следующая по максимальности длина потенциального наибольшего общего префикса
*'''Время работы'''
