Алгоритм Манакера - История изменений

Ctrlalt в 16:20, 20 декабря 2022

2022-12-20T16:20:45Z

← Предыдущая версия		Версия от 16:20, 20 декабря 2022
Строка 59:		Строка 59:
	}		}
	\|}		\|}

			== Ссылки ==
			Теория:
			* [http://e-maxx.ru/algo/palindromes_count e-maxx.ru — Нахождение всех подпалиндромов за O(N)]
			* [https://cp-algorithms.com/string/manacher.html cp-algorithms.com — Manacher's Algorithm]
			* [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%9C%D0%B0%D0%BD%D0%B0%D0%BA%D0%B5%D1%80%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Манакера]
			* [https://algorithmica.org/ru/palindromes algorithmica.org — Палиндромы]
			* [https://usaco.guide/adv/string-search?lang=cpp#manacher usaco.guide — Manacher]
			Код:
			* [https://github.com/indy256/codelibrary/blob/master/cpp/strings/manacher.cpp indy256/codelibrary/cpp/strings/manacher.cpp]
			* [https://github.com/ADJA/algos/blob/master/Strings/ManacherPalindromes.cpp ADJA/algos/Strings/ManacherPalindromes.cpp]
			Задачи:
			* [[:Категория: Задачи: Алгоритм Манакера\|Задачи: Алгоритм Манакера]]

			[[Категория:Строки]]

Ctrlalt в 16:12, 20 декабря 2022

2022-12-20T16:12:39Z

← Предыдущая версия		Версия от 16:12, 20 декабря 2022
Строка 1:		Строка 1:
	~~char~~ s~~[1000010]~~;		{\| width="100%"
	int ~~n, odd[1000010]~~, ~~even[1000010]~~;		\| width=50% \|
			vector<int> oddPalindromeCount(string &s) {
			vector<int> palindromeCount(s.size(){{Changed\|1=, 1}});
			int l, r = -1;

	~~void oddPalindromesCount() {~~		for (int i = 0; i < s.size(); i++) {
	~~int l = 0, r = -1;~~		int &p = palindromeCount[i];
	for (int i = 0; i < n; i++) {		if (i <= r)
	int k = (i > r ~~? 1 :~~ min(~~odd~~[l + r - i], r - i));		p = min(palindromeCount[l + r - i], r - i);
	while (i - ~~k >= 0~~ && i + k < n && s[i - k] == s[i + k])
	k++;		while (0 <= i - p && i + p < s.size() && s[i - p] == s[i + p])
	~~odd[i] = k;~~		p++;
	if (i + k - 1 > r) {
	l = i - k + 1;		if (i + p - 1 > r) {
	r = i + k - 1;		l = i - p {{Changed\|1=+ 1}};
			r = i + p - 1;
	}		}
	}		}

			return palindromeCount;
	}		}

			vector<vector<int>> manacher(string &s) {
			string t = "#";
			for (char c : s) {
			t += c;
			t += '#';
			}

	~~void evenPalindromesCount~~() {		vector<int> palindromeCount = oddPalindromeCount(t);
	int l ~~= 0~~, r = -1;
	for (int i = 0; i < n; i++) {		vector<vector<int>> res(2);
	int k = (i > r ~~? 0 :~~ min(~~even~~[l + r - i - 1], r - i));		for (int i = 0; i + 1 < palindromeCount.size(); i++)
	while (i - ~~k >~~= 0 && i + ~~k + 1~~ < n && s[i - k] == s[i + ~~k + 1~~])		res[i % 2].push_back(palindromeCount[i] / 2);
	k++;		return res;
	~~even[i] = k;~~		}
	if (i + k > r) {		\| width="10px" \|
	l = i - ~~k + 1~~;		\| width=50% \|
	r = i + k;		vector<int> evenPalindromeCount(string &s) {
			vector<int> palindromeCount(s.size());
			int l, r = -1;

			for (int i = 0; i < s.size(); i++) {
			int &p = palindromeCount[i];
			if (i <= r)
			p = min(palindromeCount[l + r - i {{Changed\|1=+ 1}}], r - i {{Changed\|1=+ 1}});

			while (0 <= i - p {{Changed\|1=- 1}} && i + p < s.size() && s[i - p {{Changed\|1=- 1}}] == s[i + p])
			p++;

			if (i + p - 1 > r) {
			l = i - p;
			r = i + p - 1;
	}		}
	}		}

			return palindromeCount;
	}		}
			\|}
	~~== Ссылки ==~~
	~~Теория:~~
	* [http://e-maxx.ru/algo/palindromes_count e-maxx.ru — Нахождение всех подпалиндромов за O(N)]
	~~Код:~~
	* [http://github.com/ADJA/algos/blob/master/Strings/ManacherPalindromes.cpp Algos — Manacher's algorithm]
	~~Задачи:~~
	* [[:Категория: Задачи: Алгоритм Манакера\|~~Задачи: Алгоритм Манакера]]~~

	~~[[Категория:Строки]]~~

Ctrlalt: Новая страница: « char s[1000010]; int n, odd[1000010], even[1000010]; void oddPalindromesCount() { int l = 0, r = -1; for (int i = 0; i < n; i++) { int k =…»

2015-08-15T22:47:29Z

Новая страница: « char s[1000010]; int n, odd[1000010], even[1000010]; void oddPalindromesCount() { int l = 0, r = -1; for (int i = 0; i < n; i++) { int k =…»

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

char s[1000010];
int n, odd[1000010], even[1000010];

void oddPalindromesCount() {
int l = 0, r = -1;
for (int i = 0; i < n; i++) {
int k = (i > r ? 1 : min(odd[l + r - i], r - i));
while (i - k >= 0 && i + k < n && s[i - k] == s[i + k])
k++;
odd[i] = k;
if (i + k - 1 > r) {
l = i - k + 1;
r = i + k - 1;
}
}
}

void evenPalindromesCount() {
int l = 0, r = -1;
for (int i = 0; i < n; i++) {
int k = (i > r ? 0 : min(even[l + r - i - 1], r - i));
while (i - k >= 0 && i + k + 1 < n && s[i - k] == s[i + k + 1])
k++;
even[i] = k;
if (i + k > r) {
l = i - k + 1;
r = i + k;
}
}
}

== Ссылки ==
Теория:
* [http://e-maxx.ru/algo/palindromes_count e-maxx.ru — Нахождение всех подпалиндромов за O(N)]
Код:
* [http://github.com/ADJA/algos/blob/master/Strings/ManacherPalindromes.cpp Algos — Manacher's algorithm]
Задачи:
* [[:Категория: Задачи: Алгоритм Манакера|Задачи: Алгоритм Манакера]]

[[Категория:Строки]]