Longest Common Subsequence

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

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

Q: איך מדפיסים את תת־הרצף המשותף הארוך ביותר עצמו?

מלאו את הטבלה כולה, ואז חזרו לאחור מ־ dp[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. במילה longest האותיות s ו־t מופיעות בסוף, ואילו במילה stone הן מופיעות בהתחלה, ולכן תת־רצף משותפת שמשתמשת בהן יכולה להיות רק st, שהיא קצרה יותר.

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

+19 בדיקות נסתרות בשליחה

שאלת המשך

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

רמזים

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

נפתחו 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 קריאות; במבחנים הגדולים יש 1000 אותיות בכל אחת. ובכל זאת, יש רק (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 לציין מחרוזת ריקה.

נוסחת נסיגה. משווים את האותיות האחרונות של שתי התחיליות, 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]). זהו אותו היגיון כמו ברקורסיה, כשקוראים אותה מהסוף. מקרה בסיס: השורה 0 והעמודה 0 הן 0, כי לתחילית ריקה אין שום דבר משותף עם שום דבר. סדר: כל תא קורא את התא שמעליו, את התא שמשמאלו ואת התא שמעליו ומשמאלו באלכסון, לכן במילוי שורה אחר שורה, משמאל לימין, כולם כבר יהיו מוכנים. התשובה היא dp[n][m].

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

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

אלגוריתם

צרו טבלה 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]

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

האינטואיציה

שורה i בטבלה קוראת רק את שורה i-1 ואת התאים הקודמים שלה עצמה. לאחר סיום שורה, לא קוראים שוב אף שורה שמעליה. לכן יש להשתמש בשני מערכים, prev עבור השורה שהושלמה ו-cur עבור השורה שמתמלאת, ולהחליף ביניהם אחרי כל שורה. נוסחת הנסיגה והסדר נשארים בדיוק כפי שהם.

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

האיבר הראשון בכל שורה מייצג קידומת ריקה של המחרוזת הקצרה יותר, ולכן הוא חייב להישאר 0. התשובה היא האיבר האחרון בשורה האחרונה שהושלמה.

אלגוריתם

אם 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 מייצגת את הקידומת הריקה.
כשיש התאמה, הוספת אחד ל-max(dp[i-1][j], dp[i][j-1]) במקום ל-dp[i-1][j-1]. כך אפשר להשתמש באותה אות פעמיים: עבור aa מול a יוחזר 2 במקום 1.
התאמה חמדנית באמצעות שני מצביעים. עבור cab מול abc, שתי האותיות c מותאמות זו לזו והתוצאה היא 1, בעוד שעבור ab התוצאה היא 2.
כתיבה לשורה שעדיין קוראים ממנה. כשמשתמשים בשתי שורות, כל ערך מהשורה שמעל חייב להגיע מ-prev, ו-cur[0] חייב להישאר 0.
פתרון בטעות של בעיית תת-מחרוזת משותפת ארוכה ביותר. תת-רצף יכול לדלג על אותיות; תת-מחרוזת לא יכולה.
שמירת תוצאות במטמון באמצעות רקורסיה על מחרוזות בנות 1000 אותיות. עומק הקריאות מגיע ל-2000, מעבר למגבלת ברירת המחדל של Python, שהיא 1000.

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

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

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

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

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

איך מדפיסים את תת־הרצף המשותף הארוך ביותר עצמו?

מלאו את הטבלה כולה, ואז חזרו לאחור מ־dp[n][m]. כאשר שתי האותיות בתא הנוכחי זהות, האות הזאת שייכת לתשובה: תעדו אותה וצעדו באלכסון למעלה ולשמאלה. אחרת, עברו לשכן שמעל או לשכן שמשמאל, שמכיל את הערך הגדול יותר. הפכו את סדר האותיות שתיעדתם בסוף. אי אפשר לעשות זאת בגרסה עם שתי שורות, כי היא כבר השליכה את השורות הקודמות.

מה הקשר בין LCS לכלי diff ולמרחק עריכה?

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

text1 = "stone"
text2 = "longest"

צפוי

Longest Common Subsequence

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

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

מלאו טבלת תחיליות

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

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

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

בעיות דומות