28. Find The Index of The First Occurrence in a String

Easy

Description

給定字串 haystack 和 needle，回傳 needle 在 haystack 中第一次出現的索引。若不存在回傳 -1。

Example:

Input: haystack = “sadbutsad”, needle = “sad” Output: 0 （“sad” 首次出現在 index 0）

Intuition#

核心思路：最直觀是逐位比較（Brute Force），進階可用 KMP 演算法在 O(n+m) 時間內完成。

Brute Force：對 haystack 的每個起始位置嘗試匹配 needle
KMP：預處理 needle 的 failure function（最長前後綴），利用匹配失敗時的回退資訊避免重複比較

Approaches#

1: Brute Force#

概念: 遍歷 haystack 的每個可能起始位置，逐字元比較 needle
時間複雜度: O(n * m) - n 為 haystack 長度，m 為 needle 長度
空間複雜度: O(1) - 不需額外空間

class Solution {
    fun strStr(haystack: String, needle: String): Int {
        val n = haystack.length
        val m = needle.length
        if (m > n) return -1

        for (i in 0..n - m) {
            var match = true
            for (j in 0 until m) {
                if (haystack[i + j] != needle[j]) {
                    match = false
                    break
                }
            }
            if (match) return i
        }
        return -1
    }
}

⭐2: KMP Algorithm#

概念: 建立 needle 的 prefix table（failure function），匹配失敗時根據 prefix table 跳轉，避免重新比較已知匹配的部分
時間複雜度: O(n + m) - 建表 O(m)，匹配 O(n)
空間複雜度: O(m) - prefix table

class Solution {
    fun strStr(haystack: String, needle: String): Int {
        val n = haystack.length
        val m = needle.length
        if (m == 0) return 0
        if (m > n) return -1

        // 建立 prefix table (failure function)
        val lps = IntArray(m)
        var len = 0
        var i = 1
        while (i < m) {
            if (needle[i] == needle[len]) {
                len++
                lps[i] = len
                i++
            } else {
                if (len != 0) {
                    len = lps[len - 1]
                } else {
                    lps[i] = 0
                    i++
                }
            }
        }

        // KMP 搜尋
        var hi = 0  // haystack index
        var ni = 0  // needle index
        while (hi < n) {
            if (haystack[hi] == needle[ni]) {
                hi++
                ni++
            }
            if (ni == m) {
                return hi - m
            } else if (hi < n && haystack[hi] != needle[ni]) {
                if (ni != 0) {
                    ni = lps[ni - 1]
                } else {
                    hi++
                }
            }
        }
        return -1
    }
}

KMP 的 prefix table（又稱 failure function 或 LPS 陣列）的含義：lps[i] 表示 needle[0..i] 中最長的「既是前綴又是後綴」的子字串長度。這讓匹配失敗時能跳過已知匹配的部分。

🔑 Takeaways#

Pattern: 字串搜尋 -> Brute Force 或 KMP（面試中 Brute Force 通常足夠，但理解 KMP 是加分項）
關鍵技巧: KMP 的核心在於 prefix table 的建立；Kotlin 內建的 indexOf 底層也是類似演算法