Longest Common Subsequence

Q: מהי סיבוכיות הזמן של תת־הסדרה המשותפת הארוכה ביותר?

פתרון הטבלה רץ בזמן O(n × m) , תא אחד לכל זוג של קידומות. הוא דורש זיכרון בגודל O(n × m) עבור הטבלה המלאה, או O(min(n, m)) עם שתי שורות. רקורסיה רגילה ללא טבלה היא מעריכית.

בינוניתכנון דינמי

+10

מקבלים שתי מחרוזות, text1 ו־text2. תת־רצף של מחרוזת שומר חלק מהאותיות שלה בסדר המקורי שלהן ומשמיט את השאר; האותיות שנשמרות לא חייבות להיות סמוכות. החזירו את האורך של המחרוזת הארוכה ביותר שהיא תת־רצף של שתיהן, או 0 אם אין לשתי המחרוזות אות משותפת.

פונקציה

longestCommonSubsequence(text1: string, text2: string) → integer

text1string: המחרוזת הראשונה
text2string: המחרוזת השנייה
מחזירהinteger: האורך של תת־הסדרה המשותפת הארוכה ביותר

אילוצים

1 ≤ text1.length ≤ 1000
1 ≤ text2.length ≤ 1000
שתי המחרוזות מכילות רק אותיות אנגליות קטנות.

דוגמאות

קלט: text1 = "stone"text2 = "longest"
פלט: 3
הסבר: האותיות o, n, e מופיעות בסדר הזה בשתי המילים, ולכן one משותפת להן, באורך 3. האותיות s ו־t מופיעות בסוף longest אך בתחילת stone, ולכן השימוש בהן נותן לכל היותר st.

קלט: text1 = "pear"text2 = "reap"
פלט: 2
הסבר: ea מופיע בשתי המילים. האות p והאות r נמצאות משני הצדדים של ea בשתי המילים, ולכן אף אחת מהן לא יכולה להצטרף אליו, והתשובה היא 2.

שאלת המשך

האם אפשר להחזיר אחת מתתי־הסדרות המשותפות הארוכות ביותר עצמה, יחד עם אורכה?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

התאמה חמדנית נכשלת: התאמת ה־c של cab ל־c האחרונה של abc לא משאירה דבר עבור a ו־b; דילוג עליה מוצא את ab. התשובה עבור שני קידומות תלויה בתשובות עבור קידומות קצרות יותר, ולכן טבלה בגודל (n+1) × (m+1) פותרת כל זוג פעם אחת. כל שורה קוראת רק את השורה שמעליה, ולכן מספיקות שתי שורות.

השוו בין האותיות הראשונות בעזרת רקורסיה

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

נסמן את התשובה עבור הסיומות text1[i:] ו־text2[j:] ב־lcs(i, j). אם האותיות הראשונות שלהן זהות, נזווג ביניהן: תת־רצף משותף ארוך ביותר שמדלג על הזוג הזה יכול להחליף את הזוג הראשון שלו בזוג הזה בלי להתקצר. לכן התשובה היא 1 + lcs(i+1, j+1).

אם האותיות שונות, אי אפשר להשתמש בשתיהן, כי האותיות שהן מזווגות איתן יגרמו לזוגות להצטלב. לכן אפשר להשמיט אחת מהן: max(lcs(i+1, j), lcs(i, j+1)). סיומת ריקה נותנת 0.

כל אי־התאמה מתחילה שתי קריאות. שתי מחרוזות בנות 20 אותיות ללא אות משותפת דורשות כבר כ־2.8 × 10^11 קריאות, אף שיש רק (n+1) × (m+1) זוגות שונים (i, j), ולכן כמעט כל קריאה חוזרת על קריאה קודמת.

אלגוריתם

כתבו lcs(i, j) עבור הסיומות שמתחילות ב-i וב-j.
אם i או j נמצאים אחרי סוף המחרוזת שלהם, החזירו 0.
אם text1[i] == text2[j], החזירו 1 + lcs(i+1, j+1).
אחרת, החזירו max(lcs(i+1, j), lcs(i, j+1)).
התשובה היא lcs(0, 0).

def longestCommonSubsequence(text1, text2):
    def lcs(i, j):
        # The longest common subsequence of text1[i:] and text2[j:]
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + lcs(i + 1, j + 1)
        return max(lcs(i + 1, j), lcs(i, j + 1))

    return lcs(0, 0)

מלא טבלת קידומות

האינטואיציה

נניח ש-dp[i][j] הוא התשובה עבור i האותיות הראשונות של text1 ועבור j האותיות הראשונות של text2, כך שמדד 0 מציין קידומת ריקה, והשורה 0 והעמודה 0 הן 0. משווים בין האותיות האחרונות של שתי הקידומות, text1[i-1] ו-text2[j-1]: אם האותיות שוות, מצרפים אותן בזוג, dp[i-1][j-1] + 1; אם האותיות שונות, משמיטים אחת מהן, max(dp[i-1][j], dp[i][j-1]). זוהי הרקורסיה כשקוראים אותה מהסוף.

כל תא קורא את התאים שמעליו, משמאלו ובאלכסון למעלה ומשמאל, ולכן מילוי שורה אחר שורה, משמאל לימין, מבטיח שהם כבר מוכנים. עבור pear ו-reap, השורה עבור pea היא [0, 0, 1, 2, 2]; הערך בתא שלה עבור rea הוא 2, כי a תואמת ל-a, ומוסיפים 1 לערך בתא עבור pe ו-re.

שתי מחרוזות בנות 1000 אותיות דורשות בערך 10^6 צעדים בזמן קבוע.

אלגוריתם

צרו טבלה dp של אפסים בגודל (n+1) × (m+1).
עבור i מ־1 עד n ו־j מ־1 עד m, השוו בין text1[i-1] ל־text2[j-1].
אם יש התאמה, הגדירו dp[i][j] = dp[i-1][j-1] + 1.
אחרת הגדירו dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
החזירו את dp[n][m].

def longestCommonSubsequence(text1, text2):
    n, m = len(text1), len(text2)
    # dp[i][j]: the longest common subsequence of text1[:i] and text2[:j].
    # Row 0 and column 0 stay 0: an empty prefix has nothing in common.
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

השאר רק שתי שורות

האינטואיציה

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

התשובה אינה תלויה במחרוזת שמופיעה ראשונה, לכן נריץ את השורות לאורך המחרוזת הקצרה יותר. כל שורה תכיל אז min(n, m) + 1 מספרים: 1001 במקום מיליון תאים עבור הקלטים הגדולים ביותר, עם אותן 10^6 פעולות.

אלגוריתם

אם text2 ארוכה יותר מ-text1, החליפו ביניהן.
צרו את prev ואת cur, שכל אחד מהם מכיל m + 1 אפסים, כאשר m הוא האורך הקצר יותר.
עבור כל אות ב-text1, מלאו את cur[1..m] לפי אותו כלל כמו בטבלה, תוך קריאת prev עבור השורה שמעל.
החליפו בין prev ל-cur.
החזירו את prev[m].

def longestCommonSubsequence(text1, text2):
    if len(text2) > len(text1):
        text1, text2 = text2, text1  # keep the rows as short as the shorter string
    m = len(text2)
    # prev[j]: the answer for the previous prefix of text1 and text2[:j]
    prev = [0] * (m + 1)
    for ch in text1:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if ch == text2[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

מלכודות ומקרי קצה

ערבוב בין האינדקסים של הטבלה לאינדקסים של מחרוזות. התא dp[i][j] משווה בין text1[i-1] לבין text2[j-1], כי שורה 0 מייצגת את הקידומת הריקה.
במקרה של התאמה, הוספת 1 ל־max(dp[i-1][j], dp[i][j-1]) במקום ל־dp[i-1][j-1]. כך אפשר להשתמש באותה אות פעמיים: עבור aa מול a יוחזר 2 במקום 1.
כתיבה לשורה שממנה עדיין קוראים. כשמשתמשים בשתי שורות, כל ערך מהשורה שמעל חייב להגיע מ־prev, ו־cur[0] חייב להישאר 0.
שמירת תוצאות הרקורסיה במטמון ב־Python עבור מחרוזות באורך 1000 אותיות. עומק הקריאות מגיע ל־2000, מעבר למגבלת ברירת המחדל של 1000.

שאלות נפוצות3

מהי סיבוכיות הזמן של תת־הסדרה המשותפת הארוכה ביותר?

פתרון הטבלה רץ בזמן O(n × m), תא אחד לכל זוג של קידומות. הוא דורש זיכרון בגודל O(n × m) עבור הטבלה המלאה, או O(min(n, m)) עם שתי שורות. רקורסיה רגילה ללא טבלה היא מעריכית.

מה ההבדל בין תת־רצף משותף ארוך ביותר לבין תת־מחרוזת משותפת ארוכה ביותר?

תת־רצף יכול לדלג על אותיות כל עוד הסדר נשמר; תת־מחרוזת היא רצף של אותיות סמוכות. עבור stone ו־longest, תת־הרצף המשותף הארוך ביותר הוא one (3), אך תת־המחרוזת המשותפת הארוכה ביותר היא on (2). טבלת תת־המחרוזות מאפסת תא ל־0 במקרה של אי־התאמה, במקום להעתיק תא סמוך.

איך LCS קשור לכלי diff ולמרחק עריכה?

השוואה בין שתי גרסאות של קובץ משמרת את תת־הרצף המשותף הארוך ביותר של השורות שלהן ומציגה כל שורה אחרת כשורה שנוספה או הוסרה. המספר הקטן ביותר של הוספות ומחיקות שהופכות מחרוזת אחת לאחרת הוא n + m - 2 × LCS. מרחק עריכה מאפשר גם להחליף אות, ולכן הוא זקוק לטבלה משלו.

def longestCommonSubsequence(text1, text2):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

text1 = "stone"
text2 = "longest"

הפלט הצפוי

Longest Common Subsequence

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

השוו בין האותיות הראשונות בעזרת רקורסיה

מלא טבלת קידומות

השאר רק שתי שורות

מלכודות ומקרי קצה

שאלות נפוצות3

בעיות דומות