// 演算法 / Algorithm:
// 用雙指針暴力搜尋：外層 i 枚舉 haystack 的每一個可能起點，
// 內層 j 比較 needle 的每個字元；若全部相等則回傳 i，否則繼續。
// Brute-force two-pointer scan: outer i picks a start in haystack,
// inner j compares characters with needle; return i on full match.

#include <string.h>  // 為了使用 strlen / for strlen

int strStr(char* haystack, char* needle) {
    int n = (int)strlen(haystack);   // n 是 haystack 長度，先存起來避免重複計算 / cache haystack length, strlen is O(n)
    int m = (int)strlen(needle);     // m 是 needle 長度 / cache needle length

    // 邊界：若 needle 比 haystack 長，不可能匹配；直接回傳 -1
    // Edge case: needle longer than haystack ⇒ impossible match, return -1
    if (m > n) return -1;

    // 外層 i 是 haystack 中嘗試匹配的起點；只需到 n - m 即可
    // Outer i is the candidate start in haystack; only goes up to n - m
    // 因為從更後面開始剩餘字元不夠 m 個，不可能匹配，也避免越界
    // because past that, fewer than m chars remain — impossible to match, and avoids out-of-bounds
    for (int i = 0; i <= n - m; i++) {
        int j = 0;                   // j 是 needle 內的比對指針，從 0 開始 / j scans needle from 0
        // 內層比對：只要 j 還沒走完且字元相等就繼續
        // Inner compare: advance while within needle AND chars match
        while (j < m && haystack[i + j] == needle[j]) {
            j++;                     // 多匹配了一個字元，j 前進 / one more char matched, advance j
        }
        if (j == m) {                // j 走到底 ⇒ 所有 m 個字元都匹配 / j reached m ⇒ full match
            return i;                // 回傳這個起點 / return this starting index
        }
        // 否則：內層中途遇到不匹配，外層 i 自動 +1 再試下一個起點
        // Otherwise: mismatch happened, outer loop increments i and retries
    }

    return -1;                       // 全部起點都試過仍沒找到 / tried all starts, no match
}