Find the First Occurrence in a String

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

בדיקת כל מיקום התחלה אורכת במקרה הגרוע O(n · m) זמן, כאשר n ו- m הם האורכים של מחרוזת החיפוש ומחרוזת החיפוש המבוקשת, ודורשת O(1) מקום נוסף. אלגוריתם Knuth-Morris-Pratt פועל בזמן O(n + m) ודורש O(m) מקום עבור הטבלה שלו, ללא קשר לאותיות.

קלמערכים ומחרוזות שני מצביעים

+10

מקבלים שתי מחרוזות, haystack ו-needle. החזירו את האינדקס ב-haystack שבו מתחיל המופע הראשון של needle, בספירה מ-0. אם needle אף פעם לא מופיעה ב-haystack, החזירו -1. כתבו בעצמכם את החיפוש במקום לקרוא לפונקציית חיפוש מובנית של תת-מחרוזת, כגון find או indexOf.

פונקציה

strStr(haystack: string, needle: string) → integer

haystackstring: הטקסט לחיפוש
needlestring: המחרוזת שיש לחפש
מחזירהinteger: האינדקס שבו מתחיל העותק הראשון של needle, או ‎-1‎ אם אין כזה

אילוצים

1 ≤ haystack.length ≤ 5 × 10⁴
1 ≤ needle.length ≤ 5 × 10⁴
שתי המחרוזות מכילות אותיות אנגליות קטנות בלבד.
needle עשויה להיות ארוכה יותר מ-haystack. במקרה כזה היא לא יכולה להופיע, והתשובה היא -1.

דוגמאות

קלט: haystack = "bananarama"needle = "ana"
פלט: 1
הסבר: האותיות באינדקסים 1, 2 ו־3 מרכיבות את ana. עותק שני מתחיל באינדקס 3 וחופף לראשון, אבל התשובה היא העותק הראשון, ולכן היא 1.

קלט: haystack = "pineapple"needle = "apples"
פלט: -1
הסבר: apple מתחיל באינדקס 4, ו־haystack מסתיים מיד אחריו, ולכן לאות האחרונה s של needle אין אות להתאים לה. אין עותק מלא של apples, ולכן התשובה היא -1.

קלט: haystack = "abcabcabd"needle = "abcabd"
פלט: 3
הסבר: הניסיון באינדקס 0 תואם לחמש אותיות, abcab, ואז נתקל ב-c במקום שבו המחט מצפה ל-d. העותק המתאים מתחיל באינדקס 3 ומסתיים ב-d האחרון.

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

שאלת המשך

האם תוכל להחזיר כל אינדקס שבו needle מתחיל, כולל מופעים חופפים, ועדיין בזמן O(n + m)?

רמזים

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

נפתחו 0 מתוך 3

פתרון

השוואה של needle בכל מיקום התחלה היא נכונה, אבל איטית כשכמעט מתקבלות התאמות: התאמה חלקית ארוכה שנכשלת סמוך לסופה נזרקת, ובהתחלה הבאה נקראות שוב רוב אותן אותיות. אלגוריתם Knuth-Morris-Pratt שומר את העבודה הזו. טבלה שנבנית על סמך needle בלבד מציינת כמה מההתאמה החלקית שנכשלה עדיין אפשר לנצל, כך שהסריקה לעולם אינה נעה לאחור בתוך haystack ומסתיימת בזמן O(n + m).

בדקו כל מיקום התחלה

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

האינטואיציה

נסמן את האורכים ב־n עבור haystack וב־m עבור needle. עותק של needle יכול להתחיל בכל אינדקס מ־0 עד n-m. נסה את נקודות ההתחלה האלה משמאל לימין. בכל אחת מהן, השווה בין needle ל־haystack אות אחר אות ועצור בהבדל הראשון. נקודת ההתחלה הראשונה שבה כל m האותיות זהות היא התשובה, והמעבר משמאל לימין מבטיח שזה יהיה העותק הראשון.

נקודת ההתחלה האחרונה היא n-m, כי עותק שיתחיל מאוחר יותר יחרוג מסוף haystack. אותו גבול מתאים גם למקרה שבו needle ארוכה יותר מ־haystack: אין נקודת התחלה לנסות, והלולאה מסתיימת ומחזירה -1.

העלות מורגשת כשרוב האותיות זהות. נניח שיש haystack עם 50,000 אותיות a ו־needle עם 24,999 אותיות a ואחריהן b. בכל אחת מ־25,001 נקודות ההתחלה מושוות 25,000 אותיות לפני שמגיעים ל־b, כלומר יותר מ־6 × 10^8 השוואות עבור תשובה של -1.

אלגוריתם

נסמן את אורכיהם של haystack ושל needle ב־n וב־m, בהתאמה.
עבור כל start מ־0 ועד n-m, נגדיר את j כ־0.
כל עוד j < m ו־haystack[start + j] שווה ל־needle[j], נגדיל את j.
אם j הגיע ל־m, כל האותיות תואמות: נחזיר את start.
אם אף ערך של start לא מתאים, נחזיר -1.

def strStr(haystack, needle):
    n, m = len(haystack), len(needle)
    for start in range(n - m + 1):
        j = 0
        while j < m and haystack[start + j] == needle[j]:
            j += 1
        if j == m:
            return start
    return -1

Knuth-Morris-Pratt

האינטואיציה

שימו לב למה שחיפוש בכוח גס משליך. בחיפוש אחר abcabd בתוך abcabcabd, הניסיון באינדקס 0 מתאים ל-abcab ואז נכשל. חמש האותיות האלה מסתיימות ב-ab, וגם המחט מתחילה ב-ab. לכן, לאחר אי-ההתאמה, שתי אותיות מהניסיון השימושי הבא כבר מותאמות, ואפשר להמשיך מאותו מקום במחרוזת הטקסט.

גבול של מחרוזת הוא תחילית קצרה יותר שהיא גם סיומת, כמו ab ב-abcab. לפני החיפוש, בנו טבלה lps שבה lps[i] הוא אורך הגבול הארוך ביותר של needle[0..i]. עבור abcabd היא [0, 0, 0, 1, 2, 0]. הטבלה תלויה רק במחט, ובונים אותה באמצעות אותה לולאת התאמה, שרצה על המחט מול עצמה.

לאחר מכן סרקו את מחרוזת הטקסט פעם אחת ושמרו את k, מספר אותיות המחט שהותאמו עד כה. אם האות הבאה שווה ל-needle[k], הערך של k גדל באחד. אם לא, הגדירו את k להיות lps[k-1] והשוו שוב את אותה אות, עד שהיא תתאים או ש-k יהיה 0. ירידה לגבול לעולם אינה מדלגת על מופע: כל מופע שמתחיל בתוך הניסיון שנכשל חייב להתחיל בגבול של מה שכבר הותאם, והגבול הארוך ביותר נבדק ראשון. כאשר k מגיע ל-m, המופע התחיל ב-i-m+1.

למה זה ליניארי: k עולה לכל היותר באחד עבור כל אות במחרוזת הטקסט, וכל חזרה לאחור מורידה אותו. הוא לא יכול לרדת יותר פעמים מכפי שעלה, ולכן הסריקה אורכת לכל היותר 2n צעדים, ובניית הטבלה אורכת לכל היותר 2m.

אלגוריתם

בנה את lps: כאשר k = 0, עבור כל i מ־1 עד m-1, חזור אחורה באמצעות k = lps[k-1] כל עוד k > 0 ו־needle[i] שונה מ־needle[k]; אם הם תואמים, הגדל את k; שמור את lps[i] = k.
אפס את k ל־0 ועבור על מחרוזת החיפוש עם האינדקס i.
כל עוד k > 0 ו־haystack[i] שונה מ־needle[k], קבע k = lps[k-1].
אם haystack[i] שווה ל־needle[k], הגדל את k.
אם k שווה ל־m, החזר את i-m+1. אם הלולאה מסתיימת, החזר את -1.

def strStr(haystack, needle):
    m = len(needle)
    # lps[i]: length of the longest proper prefix of needle[0..i] that is also its suffix
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and needle[i] != needle[k]:
            k = lps[k - 1]
        if needle[i] == needle[k]:
            k += 1
        lps[i] = k

    k = 0  # how many letters of needle are matched so far
    for i, ch in enumerate(haystack):
        while k > 0 and ch != needle[k]:
            k = lps[k - 1]  # fall back to the longest border, never move i back
        if ch == needle[k]:
            k += 1
        if k == m:
            return i - m + 1
    return -1

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

רוב הבאגים נמצאים בקצה של מחרוזת הטקסט או בתוך לולאת הגיבוי.

מתן אפשרות להתחלה להתקדם עד n-1 במקום עד n-m. ברגע שסוף מחרוזת הטקסט מתחיל להתאים לתחילת מחרוזת החיפוש, ההשוואה קוראת מעבר לסוף של haystack, מה שעוצר את Python, Java, Rust ו-Swift עם שגיאת אינדקס.
שוכחים שמחרוזת החיפוש יכולה להיות ארוכה יותר ממחרוזת הטקסט. עם אורכים ללא סימן, כמו size_t ב-C++ או usize ב-Rust, n-m לא יכול להיות שלילי: C++ גולש לערך עצום, ו-Rust נכנס לפאניקה בבניית ניפוי שגיאות. בדקו קודם אם m > n, או חשבו באמצעות מספרים שלמים עם סימן.
כתיבת מנגנון הגיבוי של KMP בתור if במקום while. בחיפוש aaa בתוך aabaa, התו b דורש שני צעדי גיבוי, מ-2 ל-1 ואז ל-0. אם עוצרים אחרי צעד אחד, k נשאר 1 אף על פי ש-b לא תואם לשום דבר, ומדווחים על עותק באינדקס 2 שאינו קיים.
החזרת האינדקס של מחרוזת הטקסט לאחור לאחר אי-התאמה ב-KMP. רק k משתנה. החזרת i לאחור מחזירה את המקרה הגרוע של O(n · m).
החזרת המקום שבו ההתאמה מסתיימת, או אינדקס שמתחיל ב-1. התשובה היא נקודת ההתחלה, בספירה מ-0. מחרוזות ב-Lua וב-R מתחילות ב-1, לכן החסירו 1 לפני ההחזרה.
הגדרת strStr ברמה העליונה ב-PHP. שמות פונקציות ב-PHP אינם מבחינים בין אותיות גדולות לקטנות, ולכן נוצר עימות עם הפונקציה המובנית strstr. קוד ההתחלה של PHP מציב את הפונקציה במרחב שמות משלה מסיבה זו.

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

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

בדיקת כל מיקום התחלה אורכת במקרה הגרוע O(n · m) זמן, כאשר n ו-m הם האורכים של מחרוזת החיפוש ומחרוזת החיפוש המבוקשת, ודורשת O(1) מקום נוסף. אלגוריתם Knuth-Morris-Pratt פועל בזמן O(n + m) ודורש O(m) מקום עבור הטבלה שלו, ללא קשר לאותיות.

איך פועלת טבלת הקידומות של KMP?

עבור כל קידומת של תבנית החיפוש, הטבלה שומרת את האורך של הקידומת התקינה הארוכה ביותר שלה שהיא גם סיומת. לאחר אי-התאמה כש־k אותיות כבר הותאמו, אותן k אותיות הן קידומת של תבנית החיפוש, ו־lps[k-1] מציין כמה מהן יכולות להתחיל את ההתאמה האפשרית הבאה. עבור aabaaab הטבלה היא [0, 1, 0, 1, 2, 2, 3].

למה לא להשתמש ב־find או ב־indexOf המובנים?

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

אפשר לפתור את זה באמצעות גיבוב במקום KMP?

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

Python

def strStr(haystack, needle):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

haystack = "bananarama"
needle = "ana"

צפוי