Префикс-функция - История изменений

Ctrlalt в 17:38, 13 февраля 2023

2023-02-13T17:38:09Z

← Предыдущая версия		Версия от 17:38, 13 февраля 2023
Строка 14:		Строка 14:
	Применения:		Применения:

	* Поиск подстроки 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. Новые подстроки ~~—~~ те, которые начинаются в начале строки и не встречаются далее. Вычисляем префикс-функцию s. ~~Пусть m = max~~(p~~[i]~~). В s' уже встречались все префиксы s длиной ≤ 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 уже встречались все префиксы длиной ≤ maxP, поэтому res = prevRes + (suffix.size() - maxP).

	== Ссылки ==		== Ссылки ==

Ctrlalt в 01:52, 27 марта 2021

2021-03-27T01:52:13Z

← Предыдущая версия		Версия от 01:52, 27 марта 2021
Строка 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;
	}		}

Ctrlalt: /* Ссылки */

2020-08-21T05:03:34Z

Ссылки

← Предыдущая версия		Версия от 05:03, 21 августа 2020
Строка 19:		Строка 19:
	* [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 — Префикс-функция]		* [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 — Префикс-функция]
	* [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 — Алгоритм Кнута-Морриса-Пратта]		* [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 — Алгоритм Кнута-Морриса-Пратта]
	* [~~http~~://brestprog.~~neocities.org~~/~~lections~~/prefixfunction~~.html brestprog.neocities.org —~~ Префикс-функция. Алгоритм Кнута-Морриса-Пратта]		* [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 — 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 — 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 — Курс «Алгоритмы на строках» — часть 1]		* [http://informatics.mccme.ru/course/view.php?id=29 informatics.mccme.ru — Курс «Алгоритмы на строках» — часть 1]

Ctrlalt: /* Ссылки */

2020-01-02T18:50:46Z

Ссылки

← Предыдущая версия		Версия от 18:50, 2 января 2020
Строка 20:		Строка 20:
	* [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 — Алгоритм Кнута-Морриса-Пратта]		* [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 — Алгоритм Кнута-Морриса-Пратта]
	* [http://brestprog.neocities.org/lections/prefixfunction.html brestprog.neocities.org — Префикс-функция. Алгоритм Кнута-Морриса-Пратта]		* [http://brestprog.neocities.org/lections/prefixfunction.html brestprog.neocities.org — Префикс-функция. Алгоритм Кнута-Морриса-Пратта]
			* [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 — Searching substring in O(N). Knuth–Morris–Pratt algorithm + prefix function]		* [http://github.com/indy256/codelibrary/blob/master/java/src/Kmp.java CodeLibrary — Searching substring in O(N). Knuth–Morris–Pratt algorithm + prefix function]

Alvelcom в 04:47, 3 февраля 2016

2016-02-03T04:47:03Z

← Предыдущая версия		Версия от 04:47, 3 февраля 2016
Строка 13:		Строка 13:
	* Определение минимального периода m строки s за O(N). m = \|s\| - p[\|s\| - 1].		* Определение минимального периода m строки s за O(N). m = \|s\| - p[\|s\| - 1].
	* Определение числа различных подстрок n строки s за O(N^2). Пусть известен ответ n' для s' = s[1 .. \|s\| - 1], за O(N) вычислим ответ для s. Новые подстроки — те, которые начинаются в начале строки и не встречаются далее. Вычисляем префикс-функцию s. Пусть m = max(p[i]). В s' уже встречались все префиксы s длиной ≤ m, поэтому n = n' + (\|s\| - m).		* Определение числа различных подстрок n строки s за O(N^2). Пусть известен ответ n' для s' = s[1 .. \|s\| - 1], за O(N) вычислим ответ для s. Новые подстроки — те, которые начинаются в начале строки и не встречаются далее. Вычисляем префикс-функцию s. Пусть m = max(p[i]). В s' уже встречались все префиксы s длиной ≤ m, поэтому n = n' + (\|s\| - m).

	~~Тест~~

	== Ссылки ==		== Ссылки ==

Alvelcom в 04:46, 3 февраля 2016

2016-02-03T04:46:40Z

← Предыдущая версия		Версия от 04:46, 3 февраля 2016
Строка 13:		Строка 13:
	* Определение минимального периода m строки s за O(N). m = \|s\| - p[\|s\| - 1].		* Определение минимального периода m строки s за O(N). m = \|s\| - p[\|s\| - 1].
	* Определение числа различных подстрок n строки s за O(N^2). Пусть известен ответ n' для s' = s[1 .. \|s\| - 1], за O(N) вычислим ответ для s. Новые подстроки — те, которые начинаются в начале строки и не встречаются далее. Вычисляем префикс-функцию s. Пусть m = max(p[i]). В s' уже встречались все префиксы s длиной ≤ m, поэтому n = n' + (\|s\| - m).		* Определение числа различных подстрок n строки s за O(N^2). Пусть известен ответ n' для s' = s[1 .. \|s\| - 1], за O(N) вычислим ответ для s. Новые подстроки — те, которые начинаются в начале строки и не встречаются далее. Вычисляем префикс-функцию s. Пусть m = max(p[i]). В s' уже встречались все префиксы s длиной ≤ m, поэтому n = n' + (\|s\| - m).

			Тест

	== Ссылки ==		== Ссылки ==

Ctrlalt: /* Ссылки */

2016-01-27T20:17:15Z

Ссылки

← Предыдущая версия		Версия от 20:17, 27 января 2016
Строка 19:		Строка 19:
	* [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 — Префикс-функция]		* [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 — Префикс-функция]
	* [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 — Алгоритм Кнута-Морриса-Пратта]		* [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 — Алгоритм Кнута-Морриса-Пратта]
			* [http://brestprog.neocities.org/lections/prefixfunction.html brestprog.neocities.org — Префикс-функция. Алгоритм Кнута-Морриса-Пратта]
	Код:		Код:
	* [http://github.com/indy256/codelibrary/blob/master/java/src/Kmp.java CodeLibrary — Searching substring in O(N). Knuth–Morris–Pratt algorithm + prefix function]		* [http://github.com/indy256/codelibrary/blob/master/java/src/Kmp.java CodeLibrary — Searching substring in O(N). Knuth–Morris–Pratt algorithm + prefix function]

Ctrlalt в 14:22, 22 июля 2015

2015-07-22T14:22:45Z

← Предыдущая версия		Версия от 14:22, 22 июля 2015
Строка 11:		Строка 11:

	* Поиск подстроки s в тексте t за O(N) (алгоритм Кнута-Морриса-Пратта). Составляется строка s#t, вычисляется её префикс-функция. Вхождения завершаются в позициях, для которых p[i] == \|s\|.		* Поиск подстроки s в тексте t за O(N) (алгоритм Кнута-Морриса-Пратта). Составляется строка s#t, вычисляется её префикс-функция. Вхождения завершаются в позициях, для которых p[i] == \|s\|.
	* Определение минимального m ~~period~~ строки s за O(N). m = \|s\| - p[\|s\| - 1].		* Определение минимального периода m строки s за O(N). m = \|s\| - p[\|s\| - 1].
	* Определение числа различных подстрок n строки s за O(N^2). Пусть известен ответ n' для s' = s[1 .. \|s\| - 1], за O(N) вычислим ответ для s. Новые подстроки — те, которые начинаются в начале строки и не встречаются далее. Вычисляем префикс-функцию s. Пусть m = max(p[i]). В s' уже встречались все префиксы s длиной ≤ m, поэтому n = n' + (\|s\| - m).		* Определение числа различных подстрок n строки s за O(N^2). Пусть известен ответ n' для s' = s[1 .. \|s\| - 1], за O(N) вычислим ответ для s. Новые подстроки — те, которые начинаются в начале строки и не встречаются далее. Вычисляем префикс-функцию s. Пусть m = max(p[i]). В s' уже встречались все префиксы s длиной ≤ m, поэтому n = n' + (\|s\| - m).

Ctrlalt: Новая страница: «Префикс-функция строки s — массив длин максимальных бордеров всех префиксов s. Бордер &…»

2015-07-16T05:31:51Z

Новая страница: «Префикс-функция строки s — массив длин максимальных бордеров всех префиксов s. Бордер &…»

Новая страница

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

for (int i = 1; i < n; i++) {
int border = p[i - 1];
while (border > 0 && s[i] != s[border])
border = p[border - 1];
p[i] = border + (s[i] == s[border]);
}

Применения:

* Поиск подстроки s в тексте t за O(N) (алгоритм Кнута-Морриса-Пратта). Составляется строка s#t, вычисляется её префикс-функция. Вхождения завершаются в позициях, для которых p[i] == |s|.
* Определение минимального m period строки s за O(N). m = |s| - p[|s| - 1].
* Определение числа различных подстрок n строки s за O(N^2). Пусть известен ответ n' для s' = s[1 .. |s| - 1], за O(N) вычислим ответ для s. Новые подстроки — те, которые начинаются в начале строки и не встречаются далее. Вычисляем префикс-функцию s. Пусть m = max(p[i]). В s' уже встречались все префиксы s длиной ≤ m, поэтому n = n' + (|s| - m).

== Ссылки ==
Теория:
* [http://e-maxx.ru/algo/prefix_function e-maxx.ru — Префикс-функция. Алгоритм Кнута-Морриса-Пратта]
* [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 — Префикс-функция]
* [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 — Алгоритм Кнута-Морриса-Пратта]
Код:
* [http://github.com/indy256/codelibrary/blob/master/java/src/Kmp.java CodeLibrary — Searching substring in O(N). Knuth–Morris–Pratt algorithm + prefix function]
* [http://github.com/ADJA/algos/blob/master/Strings/PrefixFunction.cpp Algos — Prefix function]
Задачи:
* [http://informatics.mccme.ru/course/view.php?id=29 informatics.mccme.ru — Курс «Алгоритмы на строках» — часть 1]
* [[:Категория:Задачи: Префикс-функция|Задачи: Префикс-функция]]

[[Category: Строки]]