题目描述

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
给定子字符串和母字符串，返回子字符串在母字符串第一次出现的位置，没有出现返回-1

代码及注释

class Solution {
public:
    int strStr(string haystack, string needle) {
        // 如果要求查找的字符串是空值的话，返回0
        if(needle.empty())  return 0;   
        // 子字符串在母字符串里最晚出现是子字符串正好在最后，这个位置定义为N
        const int N = haystack.size() - needle.size() + 1;
        // 从母字符串第一个位置到第N个位置，开始暴力搜索子字符串
        for(int i = 0; i<N; i++){
            //i指针在外部控制母字符串迭代位置，内部需要一个j接收i，防止影响外部变化
            int j = i; 
            // k控制子字符串位置
            int k = 0;
            // 三个停止条件，前两个限制j和k，最后一个等值匹配
            while(j<haystack.size() && k<needle.size() && haystack[j]==needle[k]){
                j++;
                k++;
            }
            // 外部迭代停止条件，当前找到的等值字符串大小恰好等于子字符串
            if(k == needle.size())  return i;
        }
        return -1;   
    }
};

分析