Find the First Occurrence in a String

Q: Apa kompleksitas waktu untuk menemukan kemunculan pertama string?

Memeriksa setiap posisi awal membutuhkan waktu O(n · m) dalam kasus terburuk dan ruang ekstra O(1) , dengan n dan m sebagai panjang haystack dan needle. Knuth-Morris-Pratt membutuhkan waktu O(n + m) dan ruang O(m) untuk tabelnya.

MudahArray dan string Two pointers

+10

Kamu mendapatkan dua string, haystack dan needle. Kembalikan indeks di haystack tempat kemunculan pertama needle dimulai, dihitung dari 0. Jika needle tidak pernah muncul di haystack, kembalikan -1. Tulis sendiri pencariannya, jangan panggil pencarian substring bawaan seperti find atau indexOf.

Fungsi

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

haystackstring: teks yang ingin dicari
needlestring: string yang dicari
Mengembalikaninteger: indeks tempat salinan pertama needle dimulai, atau -1 jika tidak ada

Batasan

1 ≤ haystack.length ≤ 5 × 10⁴
1 ≤ needle.length ≤ 5 × 10⁴
Kedua string hanya berisi huruf kecil dalam alfabet Inggris.
needle mungkin lebih panjang daripada haystack. Dalam kasus itu, needle tidak mungkin muncul, dan jawabannya adalah -1.

Contoh

Input: haystack = "bananarama"needle = "ana"
Output: 1
Penjelasan: Huruf pada indeks 1 hingga 3 membentuk ana. Salinan lainnya dimulai pada indeks 3 dan bertumpang tindih dengannya, tetapi salinan pertama yang dihitung, jadi jawabannya adalah 1.

Input: haystack = "pineapple"needle = "apples"
Output: -1
Penjelasan: apple dimulai pada indeks 4, tetapi haystack berakhir tepat setelahnya, jadi s terakhir dari needle tidak memiliki apa pun untuk dicocokkan. Jawabannya adalah -1.

Input: haystack = "abcabcabd"needle = "abcabd"
Output: 3
Penjelasan: Upaya pada indeks 0 cocok dengan abcab, lalu menemui c saat needle mengharapkan d. Salinan pada indeks 3 cocok dengan keenam huruf.

Pertanyaan lanjutan

Bisakah kamu mengembalikan setiap indeks tempat needle dimulai, termasuk kemunculan yang saling tumpang tindih, tetap dalam waktu O(n + m)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Memeriksa setiap posisi awal memang benar, tetapi kecocokan parsial yang gagal di dekat akhirnya akan dibuang, lalu posisi awal berikutnya membaca ulang huruf yang sama. Algoritma Knuth-Morris-Pratt mempertahankan pekerjaan itu: tabel yang dibuat dari needle menunjukkan seberapa banyak kecocokan yang gagal masih diperhitungkan, sehingga pemindaian tidak pernah bergerak mundur dan berjalan dalam O(n + m).

Periksa setiap posisi awal

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Sebut panjangnya n dan m. Salinan dapat dimulai pada indeks mana pun dari 0 hingga n-m; jika dimulai lebih jauh, salinan akan melewati akhir. Coba posisi awal dari kiri ke kanan, bandingkan huruf satu per satu hingga menemukan perbedaan pertama. Kecocokan penuh pertama adalah salinan pertama, dan jika needle lebih panjang daripada haystack, tidak ada posisi awal yang dapat dicoba.

Haystack dengan 50,000 a dan needle dengan 24,999 a lalu satu b menghasilkan 25,001 posisi awal dengan masing-masing 25,000 perbandingan: lebih dari 6 × 10^8 perbandingan untuk jawaban -1.

Algoritma

Misalkan panjang haystack dan needle adalah n dan m.
Untuk setiap start dari 0 hingga n-m, tetapkan j ke 0.
Selama j < m dan haystack[start + j] sama dengan needle[j], tambah j.
Jika j mencapai m, semua huruf cocok: kembalikan start.
Jika tidak ada nilai start yang berhasil, kembalikan -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

Intuisi

Saat mencari abcabd di abcabcabd, percobaan pada indeks 0 cocok dengan abcab lalu gagal. Huruf-huruf itu berakhir dengan ab, sama seperti awal pola yang dicari, jadi percobaan berguna berikutnya sudah memiliki dua huruf yang cocok dan kamu melanjutkan dari posisi yang sama pada teks.

Border dari sebuah string adalah prefiks yang lebih pendek dan juga merupakan sufiks, seperti ab pada abcab. lps[i] adalah panjang border terpanjang dari needle[0..i]; untuk abcabd, nilainya adalah [0, 0, 0, 1, 2, 0]. Setelah ketidakcocokan saat k huruf sudah cocok, turunkan k menjadi lps[k-1] lalu bandingkan huruf yang sama lagi. Tidak ada kemunculan yang dilewati: kemunculan yang dimulai di dalam percobaan yang gagal diawali dengan border dari bagian yang sudah cocok, dan border terpanjang dicoba terlebih dahulu.

k naik paling banyak satu kali untuk setiap huruf pada teks, dan setiap langkah mundur menurunkannya, jadi pemindaian memerlukan paling banyak 2n langkah.

Algoritma

Buat lps: dengan k = 0, untuk i dari 1 hingga m-1, tetapkan k = lps[k-1] selama k > 0 dan needle[i] != needle[k]; jika cocok, tingkatkan k; simpan lps[i] = k.
Atur ulang k menjadi 0 dan telusuri haystack dengan indeks i.
Selama k > 0 dan haystack[i] != needle[k], tetapkan k = lps[k-1].
Jika haystack[i] sama dengan needle[k], tingkatkan k.
Jika k sama dengan m, kembalikan i-m+1. Jika perulangan berakhir, kembalikan -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

Jebakan dan kasus tepi

Membiarkan perulangan awal berjalan hingga n-1, bukan n-m. Ketika akhir haystack cocok dengan awal needle, perbandingan membaca melewati akhir.
Menghitung n-m dengan panjang unsigned (size_t di C++, usize di Rust) saat needle lebih panjang: C++ melingkar ke angka yang sangat besar dan Rust panic dalam build debug. Periksa m > n terlebih dahulu.
Menulis fallback KMP sebagai if, bukan while. Saat mencari aaa dalam aabaa, b memerlukan dua fallback. Jika berhenti setelah satu, kamu melaporkan salinan palsu pada indeks 2.
Mengembalikan indeks haystack setelah terjadi ketidakcocokan. Hanya k yang berubah. Menggerakkan i mundur akan mengembalikan kompleksitas O(n · m).
Mengembalikan indeks berbasis 1 di Lua atau R.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu untuk menemukan kemunculan pertama string?

Memeriksa setiap posisi awal membutuhkan waktu O(n · m) dalam kasus terburuk dan ruang ekstra O(1), dengan n dan m sebagai panjang haystack dan needle. Knuth-Morris-Pratt membutuhkan waktu O(n + m) dan ruang O(m) untuk tabelnya.

Bagaimana cara membuat tabel prefiks KMP?

Jalankan perulangan pencocokan pada needle dengan dirinya sendiri. Telusuri i mulai dari 1, pertahankan k sebagai panjang border saat ini, mundur dengan k = lps[k-1] jika tidak cocok, lalu simpan k di lps[i]. Untuk aabaaab, tabelnya adalah [0, 1, 0, 1, 2, 2, 3].

Bisakah kamu menyelesaikannya dengan hashing, bukan KMP?

Ya, dengan Rabin-Karp. Pertahankan hash bergulir untuk setiap jendela yang terdiri dari m huruf haystack, perbarui dalam waktu konstan saat jendela bergeser, dan bandingkan huruf hanya ketika hash-nya sama dengan hash needle. Algoritma ini berjalan dalam waktu ekspektasian O(n + m); banyaknya tabrakan membuat waktunya mendekati O(n · m).

def strStr(haystack, needle):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

haystack = "bananarama"
needle = "ana"

Output yang diharapkan