A Manacher-algoritmus egy hatékony módszer arra, hogy egy adott szövegben minden pozícióra meghatározza a leghosszabb palindrómát, amely azon a pozíción keresztül halad. Az algoritmus időbonyolultsága (O(n)), ahol (n) a szöveg hossza. Ez jelentősen gyorsabb, mint egy naiv (O(n^2))-es megközelítés.
function Manacher(s):
T = átalakított_bemenet(s) # Pl. "#a#b#b#a#"
n = T hossza
P = * n # Palindróma sugarak
C = 0 # Aktuális középpont
R = 0 # Jobb határ
minden i 0-tól n-1-ig:
tükrözött = 2 * C - i # Tükrözött pozíció C-hez képest
ha i < R:
P = min(R - i, P) # Tükrözött érték felhasználása
# Próbáld bővíteni a palindrómát
amíg T + 1] == T - 1]:
P += 1
# Frissítsd C-t és R-t, ha szükséges
ha i + P > R:
C = i
R = i + P
térj vissza P
def manacher(s):
# Átalakított szöveg (# karakterekkel)
t = "#" + "#".join(s) + "#"
n = len(t)
p = * n # Palindrómák sugarai
C, R = 0, 0 # Középpont és jobb határ
for i in range(n):
mirr = 2 * C - i # Tükrözött pozíció
if i < R:
p = min(R - i, p)
# Palindróma bővítése
while i + p + 1 < n and i - p - 1 >= 0 and t + 1] == t - 1]:
p += 1
# Frissítsd a középpontot és a jobb határt
if i + p > R:
C, R = i, i + p
# Eredeti palindrómák kinyerése
max_length = max(p)
center_index = p.index(max_length)
start = (center_index - max_length) // 2
return s, max_length
# Példa használat
s = "babad"
longest_palindrome, length = manacher(s)
print(f"Leghosszabb palindróma: {longest_palindrome}, Hossza: {length}")
Kimenet:
Leghosszabb palindróma: bab, Hossza: 3
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
pair<string, int> manacher(const string& s) {
// Átalakított szöveg
string t = "#";
for (char c : s) {
t += c;
t += "#";
}
int n = t.size();
vector<int> p(n, 0); // Palindrómák sugarai
int C = 0, R = 0; // Középpont és jobb határ
for (int i = 0; i < n; i++) {
int mirr = 2 * C - i; // Tükrözött pozíció
if (i < R) {
p = min(R - i, p);
}
// Palindróma bővítése
while (i + p + 1 < n && i - p - 1 >= 0 && t + 1] == t - 1]) {
p++;
}
// Frissítsd a középpontot és a jobb határt
if (i + p > R) {
C = i;
R = i + p;
}
}
// Eredeti palindrómák kinyerése
int max_length = *max_element(p.begin(), p.end());
int center_index = max_element(p.begin(), p.end()) - p.begin();
int start = (center_index - max_length) / 2;
return {s.substr(start, max_length), max_length};
}
int main() {
string s = "babad";
auto result = manacher(s);
cout << "Leghosszabb palindróma: " << result.first << ", Hossza: " << result.second << endl;
return 0;
}
Kimenet:
Leghosszabb palindróma: bab, Hossza: 3
A Manacher-algoritmus gyors és hatékony megoldást nyújt a leghosszabb palindrómák keresésére: - Időbonyolultság: (O(n)), köszönhetően a tükrözés és jobb határ használatának. - Előny: Minden palindrómát megtalál egyetlen futtatás alatt, függetlenül a bemeneti szöveg hosszától. - Alkalmazás: Szövegelemzés, bioinformatika, karakterlánc-problémák optimalizálása.