LintCode 字串查找：實現 strStr 函數完整解析

字串查找（又稱子字串搜尋）是字串操作中極為實用的功能。任務要求在來源字串 source 中找出目標字串 target 首次出現的起始索引（從 0 開始計算），若不存在則返回 -1。

範例說明

• source = "source", target = "target" → 返回 -1
• source = "abcdabcdefg", target = "bcd" → 返回 1

C++ 參考實作

class Solution {
public:
    int strStr(const char *source, const char *target) {
        int result = -1;
        int i = 0, j = -1;
        
        if (source == nullptr || target == nullptr) return result;
        if (*target == '\0') return i;  // 空目標字串直接返回 0
        
        while (*source != '\0') {
            ++j;
            if (*source == *target) {
                i = j;
                const char *p = source;
                const char *q = target;
                while (*p == *q) {
                    if (*(q + 1) == '\0') return i;  // 完全匹配
                    ++p; ++q;
                }
            }
            ++source;
            ++i;
        }
        return result;
    }
};

核心邏輯解析

演算法採用雙指針遍歷：外層迴圈遍歷 source，內層在發現首字元匹配時嘗試完整比對。若 target 為空字串，依題目定義返回 0。時間複雜度最壞情況為 O(m×n)，m、n 分別為兩字串長度。實務上可考慮 KMP、Boyer-Moore 等更高效演算法。

注意事項

• 空指針檢查不可省略
• 空目標字串的邊界條件處理
• 指針運算需確保不越界