668
правок
Изменения
→Псевдокод
===Псевдокод===
'''string ''' s; vector<'''int'''> p; '''for (int i = 0; i < ..p.size(); i++- 1)'''
{
'''if '' (p[i] == 0) {
s += new char;
}
===Доказательство корректности алгоритма===
Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией.(также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну из них).