1. 题目
28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
题目描述
给你两个字符串haystack和needle，在haystack字符串中找出needle字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回-1。
示例
输入：haystack = "sadbutsad", needle = "sad"
输出：0
输入：haystack = "leetcode", needle = "leeto"
输出：-1
约束
(1 <= haystack.length, needle.length <= 10^4)
haystack和needle仅由小写英文字符组成
2. 最佳解题思路描述（暴力双指针朴素匹配，适合入门）
遍历主串每个下标
i，当haystack[i] == needle[0]时，开启子串匹配；从 i 开始连续比对 len(needle) 个字符：
全部匹配成功：直接返回起始下标
i；中途字符不相等：匹配失败，重置标记继续外层循环；
遍历结束无匹配返回
-1。
优势
逻辑直白，容易手写；无需复杂 KMP 预处理；适合题目数据范围。
时间复杂度最坏 (O(n*m))，空间 (O(1))。
3. 我的可优化代码（逻辑大体正确，存在边界 bug 与冗余变量）
class Solution { public: int strStr(string haystack, string needle) { int len = needle.size(); int num = 0; int index = -1; int flag = 0; for(int i = 0;i<haystack.size();i++){ if(haystack[i]==needle[0]){ index = i; for(int j = i;j<i+len;j++){ if(haystack[j] == needle[j-i]){ } else{ index = -1; break; } } } if(index!=-1){ break; } } return index; } };代码问题说明
数组越界风险（致命 bug）
内层循环
j < i + len没有限制j < haystack.size()。若主串剩余字符不足
len个，haystack[j]访问越界，程序崩溃。例：haystack="abc", needle="bcd"，i=1 时 i+len=4，j 取到 3 超出下标。
无效冗余变量
num、flag定义后全程未使用，无意义，可直接删除。空循环体可读性差
相等时无操作，仅不相等才处理，逻辑阅读困难。
循环范围可剪枝优化
外层
i最多只需走到haystack.size() - len，超过该起点不可能完整容纳子串，减少无效循环。
4. 规范修正版代码（朴素暴力匹配，修复越界）
class Solution { public: int strStr(string haystack, string needle) { int n = haystack.size(); int m = needle.size(); // 剪枝：i最大到 n-m，再往后长度不够 for (int i = 0; i <= n - m; ++i) { bool match = true; for (int j = 0; j < m; ++j) { if (haystack[i + j] != needle[j]) { match = false; break; } } if (match) { return i; } } return -1; } };5. 总结
原代码核心匹配逻辑思路没问题，但缺少长度边界判断，存在数组越界崩溃；
优化关键点：外层循环上限设为
n-m，从根源避免内层越界；无需多余标记变量，用 bool 记录单次匹配状态更清晰；
找到匹配起点直接 return，不用额外保存 index 再 break。
6. 相关知识拓展
拓展 1：库函数极简写法（面试仅作了解）
int strStr(string haystack, string needle) { size_t pos = haystack.find(needle); return pos == string::npos ? -1 : pos; }底层封装匹配逻辑，面试不建议作为主力解法。
拓展 2：KMP 算法（高效线性匹配，大数据最优）
预处理 needle 得到 next 前缀数组，匹配失败时主串指针不回退，时间 (O(n+m))：
class Solution { public: int strStr(string haystack, string needle) { int n = haystack.size(), m = needle.size(); if(m == 0) return 0; vector<int> next(m,0); // 构建next数组 for(int i=1,j=0;i<m;i++){ while(j>0 && needle[i]!=needle[j]) j=next[j-1]; if(needle[i]==needle[j]) j++; next[i]=j; } // 匹配 for(int i=0,j=0;i<n;i++){ while(j>0 && haystack[i]!=needle[j]) j=next[j-1]; if(haystack[i]==needle[j]) j++; if(j==m) return i-m+1; } return -1; } };拓展 3：复杂度对比
朴素暴力（修正版）：最坏 (O(n*m))，(O(1))；
KMP 算法：(O(n+m))，(O(m))；
string::find：底层优化实现，实际效率很高。
拓展 4：易错点复盘
忘记限制外层 i 上限，导致内层访问主串越界；
多余无用变量增加代码冗余；
内层循环判断只处理不相等分支，可读性差。
