668
правок
Изменения
→Доказательство корректности алгоритма
<tex>1)</tex> <tex>p[n] = 0</tex>. Тогда мы добавляем новый символ, поэтому <tex>q[n]</tex> тоже будет равно <tex>0</tex>. Также, предыдущие значения <tex>q</tex> не поменяются и останутся верными.
<tex>2)</tex> <tex>p[n] > 0</tex>. Предположим, что <tex>q[n] \neq p[n] </tex>. Заметим, что подстрока с <tex>1</tex> по <tex>p[n]</tex> оканчивается на <tex>n</tex>-ом символе. По предположению индукции наш алгоритм построил правильную строку до <tex>n - 1</tex> символа, следовательно, <tex>p[n] \leqslant q[n]</tex>. Представим, что <tex>q[n] > p[n] </tex>, тогда получается, что префикс с <tex>1..q[n]</tex> в строке <tex>s'</tex>, является подстрокой заканчивающийся на <tex>n</tex>-ом символе, но тогда возникает противоречие с тем, что массив <tex>p</tex> корректный . Также, предыдущие значения <tex>q</tex> не поменяются и останутся верными.
Простой пример некорректного <tex>p = {0,1,1} </tex>, тогда по алгоритму получится строка <tex>aaa</tex>. Очевидно, что префикс-функции не будут совпадать.
