Префикс-функция: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
Префикс-функция строки s — массив длин максимальных бордеров всех префиксов s. Бордер — собственный префикс, одновременно являющийся собственным суффиксом.
Префикс-функция строки s — массив длин максимальных бордеров всех префиксов s. Бордер — собственный префикс, одновременно являющийся собственным суффиксом.


  for (int i = 1; i < n; i++) {
  vector<int> prefixFunction(const string &s) {
    int border = p[i - 1];
    vector<int> p(s.size());
    while (border > 0 && s[i] != s[border])
    for (int i = 1; i < s.size(); i++) {
        border = p[border - 1];
        int border = p[i - 1];
    p[i] = border + (s[i] == s[border]);
        while (border > 0 && s[i] != s[border])
            border = p[border - 1];
        p[i] = border + (s[i] == s[border]);
    }
    return p;
  }
  }


Применения:
Применения:


* Поиск подстроки s в тексте t за O(N) (алгоритм Кнута-Морриса-Пратта). Составляется строка s#t, вычисляется её префикс-функция. Вхождения завершаются в позициях, для которых p[i] == |s|.
* Поиск подстроки pattern в тексте text за O(N) (алгоритм Кнута-Морриса-Пратта). Составляется строка pattern#text, вычисляется её префикс-функция. Вхождения завершаются в позициях, для которых p[i] == pattern.size().
* Определение минимального периода m строки s за O(N). m = |s| - p[|s| - 1].
* Определение минимального периода period строки s за O(N). period = s.size() - p.back().
* Определение числа различных подстрок n строки s за O(N^2). Пусть известен ответ n' для s' = s[1 .. |s| - 1], за O(N) вычислим ответ для s. Новые подстроки &mdash; те, которые начинаются в начале строки и не встречаются далее. Вычисляем префикс-функцию s. Пусть m = max(p[i]). В s' уже встречались все префиксы s длиной &le; m, поэтому n = n' + (|s| - m).
* Определение числа различных подстрок строки s за O(N^2). Пусть известен ответ prevRes для строки prevSuffix = s.substr(i + 1), за O(N) вычислим ответ res для строки suffix = s.substr(i). Новые подстроки те, которые начинаются в начале строки и не встречаются далее. Вычисляем префикс-функцию для suffix, пусть maxP = *max_element(p.begin(), p.end()). В prevSuffix уже встречались все префиксы длиной &le; maxP, поэтому res = prevRes + (suffix.size() - maxP).


== Ссылки ==
== Ссылки ==
Строка 19: Строка 23:
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F neerc.ifmo.ru/wiki &mdash; Префикс-функция]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F neerc.ifmo.ru/wiki &mdash; Префикс-функция]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%BD%D1%83%D1%82%D0%B0-%D0%9C%D0%BE%D1%80%D1%80%D0%B8%D1%81%D0%B0-%D0%9F%D1%80%D0%B0%D1%82%D1%82%D0%B0 neerc.ifmo.ru/wiki &mdash; Алгоритм Кнута-Морриса-Пратта]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%BD%D1%83%D1%82%D0%B0-%D0%9C%D0%BE%D1%80%D1%80%D0%B8%D1%81%D0%B0-%D0%9F%D1%80%D0%B0%D1%82%D1%82%D0%B0 neerc.ifmo.ru/wiki &mdash; Алгоритм Кнута-Морриса-Пратта]
* [http://brestprog.neocities.org/lections/prefixfunction.html brestprog.neocities.org &mdash; Префикс-функция. Алгоритм Кнута-Морриса-Пратта]
* [https://brestprog.by/topics/prefixfunction/ Brestprog — Префикс-функция. Алгоритм Кнута-Морриса-Пратта]
* [https://algorithmica.org/ru/string-searching Algorithmica — Префикс- и Z-функция]
* [http://brilliant.org/wiki/knuth-morris-pratt-algorithm Brilliant.org — Knuth-Morris-Pratt Algorithm]
* [http://brilliant.org/wiki/knuth-morris-pratt-algorithm Brilliant.org — Knuth-Morris-Pratt Algorithm]
Код:
Код:
* [http://github.com/indy256/codelibrary/blob/master/java/src/Kmp.java CodeLibrary &mdash; Searching substring in O(N). Knuth–Morris–Pratt algorithm + prefix function]
* [https://github.com/indy256/codelibrary/blob/master/cpp/strings/kmp.cpp github.com/indy256/codelibrary/blob/master/cpp/strings/kmp.cpp]
* [http://github.com/ADJA/algos/blob/master/Strings/PrefixFunction.cpp Algos &mdash; Prefix function]
* [http://github.com/ADJA/algos/blob/master/Strings/PrefixFunction.cpp github.com/ADJA/algos/blob/master/Strings/PrefixFunction.cpp]
Задачи:
Задачи:
* [http://informatics.mccme.ru/course/view.php?id=29 informatics.mccme.ru &mdash; Курс &laquo;Алгоритмы на строках&raquo; &mdash; часть 1]
* [http://informatics.mccme.ru/course/view.php?id=29 informatics.mccme.ru &mdash; Курс &laquo;Алгоритмы на строках&raquo; &mdash; часть 1]

Текущая версия от 17:38, 13 февраля 2023

Префикс-функция строки s — массив длин максимальных бордеров всех префиксов s. Бордер — собственный префикс, одновременно являющийся собственным суффиксом.

vector<int> prefixFunction(const string &s) {
    vector<int> p(s.size());
    for (int i = 1; i < s.size(); i++) {
        int border = p[i - 1];
        while (border > 0 && s[i] != s[border])
            border = p[border - 1];
        p[i] = border + (s[i] == s[border]);
    }
    return p;
}

Применения:

  • Поиск подстроки pattern в тексте text за O(N) (алгоритм Кнута-Морриса-Пратта). Составляется строка pattern#text, вычисляется её префикс-функция. Вхождения завершаются в позициях, для которых p[i] == pattern.size().
  • Определение минимального периода period строки s за O(N). period = s.size() - p.back().
  • Определение числа различных подстрок строки s за O(N^2). Пусть известен ответ prevRes для строки prevSuffix = s.substr(i + 1), за O(N) вычислим ответ res для строки suffix = s.substr(i). Новые подстроки — те, которые начинаются в начале строки и не встречаются далее. Вычисляем префикс-функцию для suffix, пусть maxP = *max_element(p.begin(), p.end()). В prevSuffix уже встречались все префиксы длиной ≤ maxP, поэтому res = prevRes + (suffix.size() - maxP).

Ссылки

Теория:

Код:

Задачи: