Longest Common Substring

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

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

Q: איך מחזירים את המחרוזת המשותפת הארוכה ביותר עצמה?

בכל פעם שתא מנצח את best , תעדו גם את המיקום i ב- s1 שבו הבלוק מסתיים. בסוף, תת־המחרוזת היא אותיות best של s1 שמסתיימות שם. השוואה של גדול ממש משאירה את הבלוק הראשון הארוך ביותר שנמצא ב- s1 .

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

+10

מקבלים שתי מחרוזות, s1 ו־s2. תת־מחרוזת היא רצף רציף של אותיות שנלקח ממחרוזת, כמו ork מתוך clockwork. מצאו את תת־המחרוזת הארוכה ביותר המשותפת ל־s1 ול־s2 והחזירו את האורך שלה. כשאין אות שמופיעה בשתי המחרוזות, התשובה היא 0.

פונקציה

longestCommonSubstring(s1: string, s2: string) → integer

s1string: המחרוזת הראשונה
s2string: המחרוזת השנייה
מחזירהinteger: האורך של רצף האותיות הארוך ביותר שנמצא בשתי המחרוזות

אילוצים

1 ≤ s1.length ≤ 1000
1 ≤ s2.length ≤ 1000
s1 ו-s2 מורכבים מאותיות אנגליות קטנות.

דוגמאות

קלט: s1 = "clockwork"s2 = "workshop"
פלט: 4
הסבר: work מסיימת את clockwork ומתחילה את workshop, ולכן היא מחרוזת משנה משותפת באורך 4, ולא מופיע בלוק ארוך יותר בשניהם.

קלט: s1 = "hammer"s2 = "harmed"
פלט: 2
הסבר: ha ו-me מופיעים בשתי המילים, אך אין בהן רצף של שלוש אותיות. בשתי המילים האותיות h, a, m, e מופיעות בסדר הזה, אבל ב-harmed יש r בין a ל-m.

שאלת המשך

האם אפשר לבדוק אם קיימת תת־מחרוזת משותפת באורך נתון L בזמן של בערך O(n + m) באמצעות גיבוב מתגלגל, ואז לבצע חיפוש בינארי על L?

רמזים

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

נפתחו 0 מתוך 3

פתרון

הרחבת התאמה מכל זוג נקודות התחלה גורמת לקריאה חוזרת של אותן אותיות. בדוק היכן בלוק מסתיים במקום זאת: הבלוק המשותף שמסתיים ב־s1[i] וב־s2[j] ארוך באות אחת מזה שמסתיים בשתי האותיות שלפניהם, או ריק אם האותיות שונות. טבלה של האורכים האלה נותנת את התשובה בזמן O(n × m).

הרחבה מכל זוג של מיקומי התחלה

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

האינטואיציה

כל תת־מחרוזת משותפת מתחילה במיקום כלשהו i של s1 ובמיקום כלשהו j של s2. עבור כל זוג, מתקדמים קדימה כל עוד האותיות זהות וסופרים את הצעדים; הספירה הגדולה ביותר היא התשובה.

טקסט חזרתי מאריך את ההתקדמות. כאשר שתי המחרוזות מורכבות מ־1000 עותקים של a, כל זוג מתקדם עד לסוף הסיומת הקצרה יותר: בערך 3.3 × 10^8 השוואות אותיות. ההתקדמות מ־(i, j) חוזרת על כל ההתקדמות מ־(i+1, j+1), אות אחת מאוחר יותר.

אלגוריתם

הגדר את best = 0.
עבור כל i ב־s1 וכל j ב־s2, הגדר k = 0.
כל עוד גם i+k וגם j+k נמצאים בתוך המחרוזות שלהם, וגם s1[i+k] == s2[j+k], הוסף 1 ל־k.
שמור את ערך k הגדול ביותר ב־best, והחזר אותו.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    best = 0
    for i in range(n):
        for j in range(m):
            # Walk forward while the two strings agree
            k = 0
            while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
                k += 1
            if k > best:
                best = k
    return best

טבלה של אורכי הבלוקים שמסתיימים בכל זוג

האינטואיציה

נניח ש־run[i][j] הוא האורך של המקטע המשותף הארוך ביותר שמסתיים בדיוק ב־s1[i-1] וב־s2[j-1]; בשורה 0 ובעמודה 0 הערך הוא 0. מקטע כזה חייב להכיל את שתי האותיות. אם הן שונות, לא קיים מקטע והערך בתא הוא 0. אם הן זהות, המקטע מורכב מהזוג הזה ומהמקטע שמסתיים אות אחת קודם בשתי המחרוזות: run[i-1][j-1] + 1. כל תת־מחרוזת משותפת מסתיימת במקום כלשהו, ולכן התשובה היא התא הגדול ביותר, בכל מקום שבו הוא נמצא.

עבור hammer ו־harmed, ה־h-ים נותנים 1 וה־a-ים מאריכים את המקטע ל־2, ואז ה־r קוטעת אותו. ה־m השנייה של hammer פוגשת את ה־m של harmed אחרי אי־התאמה בין m ל־r, ולכן היא מתחילה באורך 1, וה־e-ים מעלים אותו ל־2. אף תא לא מגיע ל־3.

השוואה אחת לכל תא: כמיליון עבור שתי מחרוזות בנות 1000 אותיות, לא משנה מהו הטקסט.

אלגוריתם

הקצה ל־run n+1 שורות ו־m+1 עמודות, שכולן 0, והגדר best = 0.
עבור על i בטווח 1..n, ובתוכו על j בטווח 1..m, תוך השוואה בין s1[i-1] ל־s2[j-1].
אם יש התאמה, הגדר run[i][j] = run[i-1][j-1] + 1 ועדכן את best.
אם אין התאמה, השאר את התא בתור 0.
החזר את best.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    # run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
    run = [[0] * (m + 1) for _ in range(n + 1)]
    best = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                run[i][j] = run[i - 1][j - 1] + 1
                if run[i][j] > best:
                    best = run[i][j]
            # a mismatch leaves run[i][j] at 0
    return best

שורה אחת, מעודכנת מימין לשמאל

האינטואיציה

כל תא קורא רק את התא שנמצא באלכסון מעליו ומשמאלו. לכן מערך אחד run של m+1 מספרים יכול להכיל את הטבלה אם עוברים על j מימין לשמאל: כשכותבים את run[j], המשבצת run[j-1] עדיין מכילה את הערך של האות הקודמת ב-s1, שהוא התא האלכסוני.

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

אלגוריתם

צרו מערך run של m+1 אפסים והגדירו best = 0.
עבור כל אות ch של s1, עברו על j מ־m עד 1.
אם ch == s2[j-1], הגדירו run[j] = run[j-1] + 1 ועדכנו את best.
אחרת, הגדירו run[j] = 0.
החזירו את best.

def longestCommonSubstring(s1, s2):
    m = len(s2)
    # run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
    run = [0] * (m + 1)
    best = 0
    for ch in s1:
        # Right to left, so run[j-1] still holds the value from the previous letter of s1
        for j in range(m, 0, -1):
            if ch == s2[j - 1]:
                run[j] = run[j - 1] + 1
                if run[j] > best:
                    best = run[j]
            else:
                run[j] = 0
    return best

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

החזרת התא האחרון. run[n][m] מכסה רק בלוקים שמסתיימים בשתי האותיות האחרונות. עבור abc ו־abd הערך הוא 0, ואילו עבור ab הוא 2.
העתקת השכן הגדול יותר כשיש אי־התאמה. זהו כלל תת־הרצף, והוא מאפשר לבלוק לדלג על אותיות: עבור hammer ו־harmed הוא מחזיר 4 במקום 2.
מעבר על השורה היחידה משמאל לימין. הערך האלכסוני נדרס לפני שקוראים אותו, ולכן עבור a מול aa מתקבל 2.
דילוג על האיפוס בשורה היחידה. אורך מהאות הקודמת של s1 נשמר, ובהמשך מאריך בלוק שאינו קיים.
מעבר על כוח גס ללא בדיקת גבולות. עבור zzzz מול zz מתבצעת קריאה מעבר לסוף המחרוזת הקצרה יותר.

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

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

תת־מחרוזת היא רצף רציף של אותיות; תת־רצף שומר על הסדר, אך עשויים להיות בו פערים. עבור hammer ו־harmed, אורך תת־המחרוזת המשותפת הארוכה ביותר הוא 2, ואורך תת־הרצף המשותף הארוך ביותר הוא 4 (hame). בטבלאות, אי־התאמה מאפסת את תא תת־המחרוזת, אך גורמת לתא תת־הרצף להעתיק את ערכו של השכן הגדול יותר.

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

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

איך מחזירים את המחרוזת המשותפת הארוכה ביותר עצמה?

בכל פעם שתא מנצח את best, תעדו גם את המיקום i ב-s1 שבו הבלוק מסתיים. בסוף, תת־המחרוזת היא אותיות best של s1 שמסתיימות שם. השוואה של גדול ממש משאירה את הבלוק הראשון הארוך ביותר שנמצא ב-s1.

def longestCommonSubstring(s1, s2):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

s1 = "clockwork"
s2 = "workshop"

הפלט הצפוי

Longest Common Substring

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

הרחבה מכל זוג של מיקומי התחלה

טבלה של אורכי הבלוקים שמסתיימים בכל זוג

שורה אחת, מעודכנת מימין לשמאל

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

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

בעיות דומות