Question

dynamic_programming

מחרוזת נקראת פלינדרום אם הפיכת סדר האותיות לא משנה את המחרוזת, למשל "אבא", "שלום מולש".

פורמלית, מחרוזת s1,,sns_1, \ldots, s_n מעל א"ב Σ\Sigma היא פלינדרום אם לכל i[n]i \in [n] מתקיים ש-si=sni+1s_i = s_{n - i + 1}.

מחרוזת σ1,,σm\sigma_1, \ldots, \sigma_m היא תת מחרוזת של s=s1,,sns = s_1, \ldots, s_n אם אפשר לקבל אותה על ידי מחיקת תווים מ-ss.

פורמלית, σ1,,σm\sigma_1, \ldots, \sigma_m היא תת מחרוזת של s1,,sns_1, \ldots, s_n אם קיימת פונקציה מונוטונית עולה ממש, f:[m][n]f:[m] \to [n] כך ש-σi=sf(i)\sigma_i = s_{f(i)} לכל i[m]i \in [m].

הציעו אלגוריתם שבהינתן מחרוזת ss מאורך nn מעל א"ב Σ\Sigma מוצא את אורך תת המחרוזת הארוכה ביותר של ss שהיא פלינדרום.

1

Answers

נסמן ב-f(i,j)f(i,j) את אורך תת המחרוזת הארוכה ביותר של sisjs_i \dots s_j שהיא פלינדרום.

נגדיר g(i)=max{ji:sj=si}g(i) = \max\{j \geq i : s_j = s_i\}.

נשים לב שמתקיים שעבור jij \geq i מתקיים:

f(i,j)=max{2+f(i+1,g(i)1)f(i+1,j) f(i, j) = \max \begin{cases} 2 + f(i + 1, g(i) - 1) \\ f(i + 1, j) \end{cases}

וכן עבור j<ij < i מתקיים f(i,j)=0f(i, j) = 0.

אנו מעוניינים לחשב את הערך f(1,n)f(1, n)

וניתן לחשב אותו בעזרת תכנון דינמי בטבלה בגודל n×nn \times n מהשורה התחתונה כלפי מעלה.

סיבוכיות: חישוב נאיבי שלg(i)g(i) לכל ii ניתן לעשות ב-O(n2)O(n^2). חישוב ערך של תא בודד בטבלה (בהינתן g(i)g(i)) לוקח O(1)O(1) ולכן, בסך הכל,

O(n2)O(n^2).

1
Feedback