Пре́фикс-фу́нкция от строки и позиции в ней — длина наибольшего собственного (не равного всей подстроке) префикса подстроки , который одновременно является суффиксом этой подстроки.
То есть в начале подстроки длины нужно найти такой префикс максимальной длины , который был бы суффиксом данной подстроки .
Обозначается ; где — строка; — длина подстроки в S. Считают, что .
Часто префикс-функцию определяют в векторной форме:
Пре́фикс-фу́нкция от строки есть вектор , каждый -ый элемент которого равен .
Например, для строки префикс-функция будет такой: .
Эта функция используется, например, в алгоритме Кнута — Морриса — Пратта.
Алгоритм вычисления Поиск повторяющихся слогов не в слове, а в тексте, строке начиная с первых символов? Символы строк нумеруются с 1.
Пусть . Попробуем вычислить префикс-функцию для .
Если , то, естественно, . Если нет — пробуем меньшие суффиксы. Перебирать все суффиксы линейным поиском нет необходимости. Можно воспользоваться уже посчитанными значениями префикс-функции. Можно заметить, что также будет суффиксом строки , так как — длина максимального префикса-суффикса в данной точке. Для любого строка суффиксом не будет. Таким образом, получается алгоритм: При — положить . Иначе при — положить . Иначе — установить и перейти к пункту 1.
Для строки 'abcdabcabcdabcdab' вычисление будет таким:
1 S='a', k=π=0; 2 S='b'!=S[k+1] => k=π=0; 3 S='c'!=S => k=π=0; 4 S='d'!=S => k=π=0; 5 S='a'==S => k=π=1; 6 S='b'==S => k=π=2; 7 S='c'==S => k=π=3; 8 S='a'!=S => k:=π(S, 3)=0, S==S => k=π=1; 9 S='b'==S => k=π=2; 10 S='c'==S => k=π=3; 11 S='d'==S => k=π=4; 12 S='a'==S => k=π=5; 13 S='b'==S => k=π=6; 14 S='c'==S => k=π=7; 15 S='d'!=S => k:=π(S, 7)=3, S==S => k=π=4; 16 S='a'==S => k=π=5; 17 S='b'==S => k=π=6;
И результат таков: [0,0,0,0,1,2,3,1,2,3,4,5,6,7,4,5,6].
Скорость работы Несмотря на то, что пункт 3 представляет собой внутренний цикл, время вычисления префикс-функции оценивается как . Докажем это.
Все делятся на: Увеличивающие на единицу. Цикл проходит одну итерацию. Не изменяющие нулевое . Цикл также проходит одну итерацию. Случаев 1 и 2 в сумме не более штук. Не изменяющие или уменьшающие положительное . Поскольку внутри цикла значение может только уменьшаться, а увеличение возможно лишь на единицу, то суммарно значение не может уменьшиться более, чем раза, что и ограничивает количество срабатываний внутреннего цикла.
Итого алгоритм требует не более итераций, что доказывает порядок скорости . «Худшим» для алгоритма является случай обработки строки вида 'aa…ab'.
Пример реализации на Python def prefix(s): p = * len(s) for i in range(1, len(s)): k = p[i - 1] while k > 0 and s[k] != s[i]: k = p[k - 1] if s[k] == s[i]: k += 1 p[i] = k return p
Ссылки Поиск подстроки и смежные вопросы — статья на хабрe
Категория:Строковые алгоритмы Категория:Поиск подстроки