实现strStr()

问题

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

思路

比较容易想到的思路，假设原串的长度是n，匹配串的长度是m。对原串的每一个长度为m的字串都判断是否跟匹配串一致。总共有n-m+1个子串，算法时间复杂度为O((n-m+1)m)=O(nm)

一开始，两个边界条件没有想清楚。i的范围为n-m+1，因为子串的个数为n-m+1个。

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty())
        {
            return 0;
        }
        int m = haystack.size();
        int n = needle.size();
        if(m < n)
        {
            return -1;
        }
        for(int i = 0; i < m - n + 1; ++i)
        {
            int j = 0; //在for外面定义j，j用于计数，减少一个变量的定义
            for(j = 0; j < n; ++j)
            {
                if(needle[j] != haystack[i + j])
                {
                    break;
                } 
            }
            if(j == needle.size())
            {
                return i;
            }
        }
        return -1;
    }
};

有时间的话，使用KMP算法实现一遍。KMP读一遍，过一段时间又忘，简直了。