Алгоритм Манакера
Перейти к навигации
Перейти к поиску
vector<int> oddPalindromeCount(string &s) {
vector<int> palindromeCount(s.size(), 1);
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], r - i);
while (0 <= i - p && i + p < s.size() && s[i - p] == s[i + p])
p++;
if (i + p - 1 > r) {
l = i - p + 1;
r = i + p - 1;
}
}
return palindromeCount;
}
vector<vector<int>> manacher(string &s) {
string t = "#";
for (char c : s) {
t += c;
t += '#';
}
vector<int> palindromeCount = oddPalindromeCount(t);
vector<vector<int>> res(2);
for (int i = 0; i + 1 < palindromeCount.size(); i++)
res[i % 2].push_back(palindromeCount[i] / 2);
return res;
}
|
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 + 1], r - i + 1);
while (0 <= i - p - 1 && i + p < s.size() && s[i - p - 1] == s[i + p])
p++;
if (i + p - 1 > r) {
l = i - p;
r = i + p - 1;
}
}
return palindromeCount;
}
|
Ссылки
Теория:
- e-maxx.ru — Нахождение всех подпалиндромов за O(N)
- cp-algorithms.com — Manacher's Algorithm
- neerc.ifmo.ru/wiki — Алгоритм Манакера
- algorithmica.org — Палиндромы
- usaco.guide — Manacher
Код:
Задачи: