LeetCode 實現 strStr()：Sunday 算法詳解

一、題目描述

實現字符串查找函數 strStr()。若字符串 needle 是 haystack 的子串，返回其首次出現的索引；否則返回 -1。

注意： 空字符串是所有字符串的子串，返回 0。

範例：

• 輸入：haystack = "abc", needle = "bc" → 輸出：1
• 輸入：haystack = "abc", needle = "gd" → 輸出：-1

二、解題思路：Sunday 算法

Sunday 算法是一種高效的字符串匹配算法，核心思想是利用「坏字符规则」從後向前匹配，發現不匹配時，根據主串中當前匹配窗口後一個字符在模式串中的位置決定跳躍步長。

流程示意：

主串：a b c d e f g
模式：    e f

若當前窗口不匹配，檢查主串中窗口後一個字符（此處為 'd'）是否在模式串中：

• 若不在（如 'd'），模式串直接後移 len(needle) + 1 位。
• 若在（如 'f'），將模式串中最右側的該字符與主串對齊。

三、AC 代碼（Python）

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not needle:
            return 0
        if not haystack:
            return -1
        
        i = 0
        needle_len = len(needle)
        while i <= len(haystack) - needle_len:
            if haystack[i:i+needle_len] == needle:
                return i
            # 窗口後一個字符
            if i + needle_len < len(haystack):
                next_char = haystack[i + needle_len]
                # 在模式串中從右向左查找
                try:
                    # rindex 返回最右側索引
                    offset = needle.rindex(next_char)
                    i += needle_len - offset
                except ValueError:
                    i += needle_len + 1
            else:
                break
        return -1

# 測試用例
if __name__ == "__main__":
    assert Solution().strStr("abcdefg", "ab") == 0
    assert Solution().strStr("abcdefg", "bc") == 1
    assert Solution().strStr("abcdefg", "cd") == 2
    assert Solution().strStr("abcdefg", "fg") == 5
    assert Solution().strStr("abcdefg", "bcf") == -1

四、複雜度分析

• 時間複雜度：平均 O(n/m)，最壞 O(n*m)
• 空間複雜度：O(1)

Sunday 算法在實際應用中通常比 KMP 更快，且實現簡單。