Find the First Occurrence in a String

Q: Làm thế nào để tạo bảng tiền tố KMP?

Chạy vòng lặp so khớp trên chính chuỗi kim. Duyệt i bắt đầu từ 1, giữ k làm độ dài đường viền hiện tại, lùi về bằng k = lps[k-1] khi không khớp, rồi lưu k vào lps[i] . Với aabaaab , bảng là [0, 1, 0, 1, 2, 2, 3] .

DễMảng và chuỗi Hai con trỏ

+10

Bạn nhận được hai chuỗi (string), haystack và needle. Trả về chỉ số trong haystack nơi lần xuất hiện đầu tiên của needle bắt đầu, tính từ 0. Nếu needle không bao giờ xuất hiện trong haystack, hãy trả về -1. Tự viết cách tìm kiếm thay vì gọi hàm tìm chuỗi con có sẵn như find hoặc indexOf.

Hàm

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

haystackstring: văn bản cần tìm kiếm
needlestring: chuỗi cần tìm
Trả vềinteger: chỉ số mà bản sao đầu tiên của needle bắt đầu, hoặc -1 nếu không có

Ràng buộc

1 ≤ haystack.length ≤ 5 × 10⁴
1 ≤ needle.length ≤ 5 × 10⁴
Cả hai chuỗi chỉ chứa các chữ cái tiếng Anh viết thường.
needle có thể dài hơn haystack. Khi đó, nó không thể xuất hiện, và đáp án là -1.

Ví dụ

Đầu vào: haystack = "bananarama"needle = "ana"
Đầu ra: 1
Giải thích: Các ký tự ở chỉ số từ 1 đến 3 ghép thành ana. Một bản sao khác bắt đầu ở chỉ số 3 và chồng lấp lên bản sao đó, nhưng chỉ tính bản sao đầu tiên, nên đáp án là 1.

Đầu vào: haystack = "pineapple"needle = "apples"
Đầu ra: -1
Giải thích: apple bắt đầu ở chỉ số 4, nhưng chuỗi tìm kiếm kết thúc ngay sau đó, nên ký tự s cuối cùng trong chuỗi cần tìm không có gì để khớp. Đáp án là -1.

Đầu vào: haystack = "abcabcabd"needle = "abcabd"
Đầu ra: 3
Giải thích: Lần thử ở chỉ số 0 khớp với abcab, sau đó gặp c trong khi chuỗi cần tìm yêu cầu d. Bản sao ở chỉ số 3 khớp với cả sáu ký tự.

Câu hỏi mở rộng

Bạn có thể trả về mọi chỉ số nơi needle bắt đầu, kể cả các lần xuất hiện chồng lấn, mà vẫn chạy trong thời gian O(n + m) không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Kiểm tra từng vị trí bắt đầu là chính xác, nhưng thuật toán loại bỏ phần khớp một phần bị thất bại gần cuối, rồi lượt bắt đầu tiếp theo đọc lại các chữ cái đó. Thuật toán Knuth-Morris-Pratt giữ lại phần công việc này: bảng được tạo từ needle cho biết phần nào của kết quả khớp thất bại vẫn được tính, nhờ đó quá trình quét không bao giờ lùi lại và chạy trong O(n + m).

Kiểm tra mọi vị trí bắt đầu

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Gọi độ dài là n và m. Một bản sao có thể bắt đầu tại bất kỳ chỉ số nào từ 0 đến n-m; nếu bắt đầu muộn hơn thì sẽ vượt quá phần cuối. Thử các vị trí bắt đầu từ trái sang phải, so sánh từng ký tự cho đến khi gặp điểm khác biệt đầu tiên. Kết quả khớp hoàn toàn đầu tiên là bản sao đầu tiên, còn nếu kim tìm kiếm dài hơn chuỗi chứa thì sẽ không có vị trí bắt đầu nào để thử.

Với một chuỗi chứa gồm 50.000 ký tự a và một kim tìm kiếm gồm 24.999 ký tự a, rồi đến một ký tự b, sẽ có 25.001 vị trí bắt đầu, mỗi vị trí cần 25.000 lần so sánh: hơn 6 × 10^8 lần so sánh để cho ra kết quả -1.

Thuật toán

Gọi n và m lần lượt là độ dài của haystack và needle.
Với mỗi start từ 0 đến n-m, đặt j bằng 0.
Trong khi j < m và haystack[start + j] bằng needle[j], tăng j.
Nếu j đạt đến m, mọi ký tự đều khớp: trả về start.
Nếu không có vị trí bắt đầu nào phù hợp, trả về -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

Ý tưởng

Khi tìm abcabd trong abcabcabd, lần thử ở chỉ số 0 khớp với abcab rồi thất bại. Các chữ cái đó kết thúc bằng ab, cũng là phần đầu của chuỗi cần tìm, nên lần thử hữu ích tiếp theo đã khớp sẵn hai chữ cái và bạn tiếp tục từ cùng vị trí trong chuỗi văn bản.

Biên của một chuỗi là tiền tố ngắn hơn đồng thời cũng là hậu tố, chẳng hạn ab trong abcab. lps[i] là độ dài của biên dài nhất của needle[0..i]; với abcabd, giá trị này là [0, 0, 0, 1, 2, 0]. Sau khi không khớp khi đã khớp k chữ cái, giảm k xuống lps[k-1] rồi so sánh lại cùng chữ cái đó. Không bỏ sót bản sao nào: bản sao bắt đầu bên trong lần thử thất bại sẽ bắt đầu bằng một biên của phần đã khớp, và ta thử biên dài nhất trước.

k tăng nhiều nhất một lần cho mỗi chữ cái trong chuỗi văn bản và mỗi lần lùi đều làm nó giảm, nên quá trình quét mất tối đa 2n bước.

Thuật toán

Xây dựng lps: với k = 0, cho i chạy từ 1 đến m-1, đặt k = lps[k-1] khi k > 0 và needle[i] != needle[k]; nếu khớp thì tăng k; lưu lps[i] = k.
Đặt lại k về 0 rồi duyệt chuỗi cần tìm với chỉ số i.
Khi k > 0 và haystack[i] != needle[k], đặt k = lps[k-1].
Nếu haystack[i] bằng needle[k], tăng k.
Nếu k bằng m, trả về i-m+1. Nếu vòng lặp kết thúc, trả về -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

Lỗi thường gặp và trường hợp biên

Để vòng lặp bắt đầu chạy đến n-1 thay vì n-m. Khi phần cuối của chuỗi cần tìm trùng với phần đầu của chuỗi tìm kiếm, phép so sánh sẽ đọc vượt quá phần cuối.
Tính n-m với độ dài không dấu (size_t trong C++, usize trong Rust) khi chuỗi tìm kiếm dài hơn: C++ cuộn giá trị thành một số rất lớn, còn Rust gây lỗi panic trong bản dựng gỡ lỗi. Hãy kiểm tra m > n trước.
Viết bước lùi của KMP dưới dạng if thay vì while. Khi tìm aaa trong aabaa, ký tự b cần lùi hai lần. Nếu dừng sau một lần, bạn sẽ báo nhầm có bản sao tại chỉ số 2.
Đưa chỉ số của chuỗi cần tìm lùi lại sau khi không khớp. Chỉ k thay đổi; đưa i lùi lại sẽ khiến độ phức tạp trở về O(n · m).
Trả về chỉ số bắt đầu từ 1 trong Lua hoặc R.

Câu hỏi thường gặp3

Độ phức tạp thời gian khi tìm lần xuất hiện đầu tiên của một chuỗi là bao nhiêu?

Trong trường hợp xấu nhất, việc kiểm tra mọi vị trí bắt đầu mất O(n · m) thời gian và cần thêm O(1) không gian, trong đó n và m lần lượt là độ dài của chuỗi cần tìm và chuỗi tìm kiếm. Thuật toán Knuth-Morris-Pratt mất O(n + m) thời gian và cần O(m) không gian cho bảng của nó.

Làm thế nào để tạo bảng tiền tố KMP?

Chạy vòng lặp so khớp trên chính chuỗi kim. Duyệt i bắt đầu từ 1, giữ k làm độ dài đường viền hiện tại, lùi về bằng k = lps[k-1] khi không khớp, rồi lưu k vào lps[i]. Với aabaaab, bảng là [0, 1, 0, 1, 2, 2, 3].

Bạn có thể giải bài này bằng kỹ thuật băm thay vì KMP không?

Có, với Rabin-Karp. Duy trì giá trị băm cuộn cho mỗi cửa sổ gồm m ký tự của chuỗi cần tìm, cập nhật trong thời gian hằng số khi cửa sổ trượt, rồi chỉ so sánh các ký tự khi giá trị băm của cửa sổ bằng giá trị băm của chuỗi mẫu. Thuật toán chạy trong thời gian kỳ vọng O(n + m); nếu có nhiều va chạm, thời gian có thể tăng gần đến O(n · m).

def strStr(haystack, needle):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

haystack = "bananarama"
needle = "ana"

Đầu ra mong đợi