Leghosszabb palindrom részsorozat

1. Sablon:Label

Leghosszabb palindrom részsorozat (Longest Palindromic Subsequence)

Definíció

Egy palindrom olyan szövegrészlet, amely előről és hátulról olvasva is ugyanaz. A leghosszabb palindrom részsorozat (LPS) egy adott szöveg leghosszabb olyan részsorozata, amely palindrom.

Példa:

• Szöveg: agbdba
• Leghosszabb palindrom részsorozat: abdba (hossza: 5).

Megoldás Dinamikus Programozással

A dinamikus programozási megközelítés abból áll, hogy felépítünk egy táblázatot, amelyben a részproblémák megoldásait tároljuk, így elkerülve az ismétlődő számításokat.

Algoritmus

1. Hozzunk létre egy kétdimenziós táblázatot $dp[i][j]$:

  * $dp[i][j]$ tárolja a szöveg $i$-edik és $j$-edik karakterei közötti leghosszabb palindrom részsorozat hosszát.

1. Alapeset:

  * Ha $i==j$, akkor $dp[i][j]=1$, mert egyetlen karakter önmagában is palindrom.

1. Általános eset:

  * Ha a két végén lévő karakter azonos ($s[i]==s[j]$):
    $dp[i][j]=dp[i+1][j-1]+2$
  * Ha nem azonos:
    $dp[i][j]=\max (dp[i+1][j],dp[i][j-1])$

1. Töltsük ki a táblázatot a kisebb intervallumoktól a nagyobbak felé haladva.
2. A táblázat $dp[0][n-1]$ eleme tartalmazza a leghosszabb palindrom részsorozat hosszát.

Python Implementáció

def longest_palindromic_subsequence(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    # Alapeset: minden egyes karakter önmagában palindrom
    for i in range(n):
        dp[i][i] = 1

    # Táblázat kitöltése
    for length in range(2, n + 1):  # Részszöveg hossza
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    # Leghosszabb palindrom részsorozat hossza
    return dp[0][n - 1], dp

def reconstruct_lps(s, dp):
    i, j = 0, len(s) - 1
    lps = []

    while i <= j:
        if s[i] == s[j]:
            lps.append(s[i])
            i += 1
            j -= 1
        elif dp[i + 1][j] > dp[i][j - 1]:
            i += 1
        else:
            j -= 1

    # A második fele fordított sorrendben kerül hozzáadásra
    return "".join(lps + lps[::-1][1:] if len(lps) > 1 else lps)

# Példa bemenet
s = "agbdba"
lps_length, dp = longest_palindromic_subsequence(s)
lps = reconstruct_lps(s, dp)

print("Leghosszabb palindrom részsorozat hossza:", lps_length)
print("Leghosszabb palindrom részsorozat:", lps)

Példa Kimenet

Adott szöveg: agbdba

Leghosszabb palindrom részsorozat hossza: 5
Leghosszabb palindrom részsorozat: abdba

Magyarázat

1. Táblázat építése:

  A dinamikus programozási táblázat kitöltése során a részproblémák megoldásait tároljuk, például, hogy milyen hosszú a palindrom részsorozat különböző $i$-től $j$-ig tartó intervallumokban.

1. Rekonstrukció:

  Az dp táblázat alapján visszanyerjük a tényleges palindrom részsorozatot úgy, hogy a megfelelő karaktereket hozzáadjuk a megoldáshoz.

1. Idő- és tárbonyolultság:

  * Időbonyolultság: $O(n^2)$, mivel minden $i,j$ párra végrehajtunk egy számítást.
  * Tárbonyolultság: $O(n^2)$, mivel egy $n\times n$ méretű táblázatot tárolunk.

Ez a megoldás hatékony és jól érthető, alkalmas hosszú szövegek palindrom részsorozatának meghatározására is.

Sablon:-ford- Sablon:Trans-top

• Sablon:En: Sablon:T+