Wikiszótár

Manacher-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈmɒnɒɦɛrɒlɡoritmuʃ]

Főnév

Manacher-algoritmus

  1. (matematika, algoritmusok)

Manacher-algoritmus

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.


Alapelvek

  1. Palindrómák jellemzői:
    • Egy palindróma olyan szövegrész, amely elölről és hátulról olvasva is ugyanaz (pl. “radar”, “level”).
  2. Középpont-alapú iteráció:
    • Minden pozícióra kiszámítja a leghosszabb palindrómát, amely azon keresztül halad.
  3. Tükrözés és jobb határ használata:
    • Az algoritmus a már kiszámított eredményeket újrapéldányosítja, hogy gyorsítsa a számításokat.


Működés

  1. Előkészítés:
    • A bemenetet kiegészíti speciális karakterekkel (pl. ‘#’ vagy ‘^’), hogy az egyenletes hosszúságú palindrómákat is kezelni lehessen (pl. “abba” -> “#a#b#b#a#”).
  2. Tükörszimmetria kihasználása:
    • Ha egy palindróma egy másik palindróma részhalmaza, akkor az új palindrómát részben tükrözéssel határozza meg.
  3. Megjegyzett határok:
    • Egy “jobb határ” ((R)) és egy “középpont” ((C)) segíti a számításokat:
      • (R): Az aktuálisan ismert legnagyobb hatótávolságú palindróma vége.
      • (C): Az ehhez tartozó középpont.
  4. Palindrómák kiszámítása:
    • Minden pozícióra kiszámítja a palindróma hosszát, és a (R), (C) értékeket szükség szerint frissíti.


Pszeudokód

function Manacher(s):
    T = átalakított_bemenet(s)  # Pl. "#a#b#b#a#"
    n = T hossza
    P = [0] * 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[i] = min(R - i, P[tükrözött])  # Tükrözött érték felhasználása

        # Próbáld bővíteni a palindrómát
        amíg T[i + P[i] + 1] == T[i - P[i] - 1]:
            P[i] += 1

        # Frissítsd C-t és R-t, ha szükséges
        ha i + P[i] > R:
            C = i
            R = i + P[i]

    térj vissza P

Python implementáció

def manacher(s):
    # Átalakított szöveg (# karakterekkel)
    t = "#" + "#".join(s) + "#"
    n = len(t)
    p = [0] * 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[i] = min(R - i, p[mirr])

        # Palindróma bővítése
        while i + p[i] + 1 < n and i - p[i] - 1 >= 0 and t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1

        # Frissítsd a középpontot és a jobb határt
        if i + p[i] > R:
            C, R = i, i + p[i]

    # Eredeti palindrómák kinyerése
    max_length = max(p)
    center_index = p.index(max_length)
    start = (center_index - max_length) // 2
    return s[start:start + max_length], 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

C++ implementáció

#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[i] = min(R - i, p[mirr]);
        }

        // Palindróma bővítése
        while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 && t[i + p[i] + 1] == t[i - p[i] - 1]) {
            p[i]++;
        }

        // Frissítsd a középpontot és a jobb határt
        if (i + p[i] > R) {
            C = i;
            R = i + p[i];
        }
    }

    // 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

Összegzés

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.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Manacher-algoritmus&oldid=3480333”