C++实现 strStr() 函数: 字符串搜索与面试经典问题

实现`strStr()`函数是一个经典的计算机科学问题，它要求在给定的大字符串`haystack`中查找子字符串`needle`首次出现的位置。这个函数在编程面试中经常被用来测试候选人的算法设计和字符串处理能力。题目设定的条件是，当`needle`为空字符串时，函数应返回0，这是为了遵循与C语言的`strstr()`函数和Java的`indexOf()`方法一致的行为。 该问题的核心在于设计一个高效的搜索算法，因为`haystack`和`needle`的长度可以达到最大值，即`0 <= haystack.length, needle.length <= 5 * 10^4`，且两者只包含小写英文字符。为了解决这个问题，我们可以采用线性扫描的方法，利用双指针策略。 具体步骤如下： 1. **初始化变量**：首先获取`haystack`和`needle`的长度，分别存储在整型变量`n`和`m`中。由于我们需要找到的是子串的起始位置，所以`needle`的长度会影响搜索范围。 2. **循环查找**：使用一个外层循环，让指针`i`从0开始，步长为`m`遍历`haystack`，直到`i + m > n`。这样做的原因是，每次循环都是尝试将`needle`放在`haystack`的不同可能位置进行匹配。 3. **内层循环比较**：在每次外层循环中，用一个内层循环（从`j = 0`到`j = m - 1`）逐个比较`haystack`中的字符，如果发现不匹配，设置标志`flag`为`false`并跳出内层循环。 4. **匹配检查**：如果内层循环完成后`flag`仍为`true`，说明找到了匹配，返回当前`i`作为子串在`haystack`中的位置。这是因为我们在每次循环中都在尝试`needle`的起始位置。 5. **处理边界情况**：如果没有找到匹配，当循环结束时返回-1，表示`needle`不在`haystack`中。 以下是一个用C++编写的解决方案： ```cpp class Solution { public: int strStr(string haystack, string needle) { int n = haystack.size(), m = needle.size(); for (int i = 0; i + m <= n; i++) { bool flag = true; for (int j = 0; j < m; j++) { if (haystack[i + j] != needle[j]) { flag = false; break; } } if (flag) { return i; } } return -1; } }; ``` 总结起来，`strStr()`函数的关键在于如何利用双指针优化搜索过程，避免不必要的字符比较，从而在较短的时间内找到子串在大字符串中的首次出现位置。