string-28.Implement 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      

题目解析：

1. 此题意思是：在字符串str1中寻找str2，存在的话就返回str2在str1中第一次出现的手位置，不存在的话就返回-1。

2.此题最简单易懂的方法是：从str1的每一个位置i开始，依次向后比对str2的位置。此种方法的时间复杂度就是O(str1.size()*str2.size())。需要的时间复杂度是O(1)。

3. 解决此问题，可以利用一个经典的算法——KMP算法。

  （1.）str1为匹配串，str2为模式串，在str1中寻找str2。首先，需要一个辅助数组next，next中存放的是str2中对应字符位置的共同前后缀字符个数。关于next的作用看以看这篇博客，写的很好：【next数组和KMP详解】。

  （2.）求解出next数组后，可以从str1开始进行一遍遍历，就能找出是否存在str2。

  （3.）个人理解此种KMP算法的时间复杂度是O(str1.size()+str2.size())，空间复杂度是O(str2.size());

代码如下：

class Solution {
public:
    // 借用KMP算法，可以简单方便的求解
    // 求解next数组
    void GetNextArr(string &s, int size, vector<int> &next)
    {
        next[0] = 0;
        //i:模版字符串下标；k:最大前后缀长度
        int k = next[0];
        for(int i=1; i<size; ++i)
        {
            while(k>0 && s[k] != s[i])
                k = next[k-1];
            if(s[k] == s[i])
                ++k;
            next[i] = k;
        }
        
        return;
    }
    int strStr(string haystack, string needle) 
    {
        int size1 = haystack.size();
        int size2 = needle.size();
        if(size2 == 0)
            return 0;
        if(size1 < size2 || size1 == 0)
            return -1;
        // 求解next的next数组
        vector<int> next;
        next.resize(size2);
        GetNextArr(needle, size2, next);
        // 开始匹配求解
        int j=0;
        bool bIsMatch = false;
        for(int i=0; i<size1; ++i)
        {
            while(j>0 && haystack[i] != needle[j])
                j = next[j-1];
            if(haystack[i] == needle[j] && j == size2-1)
            {
                bIsMatch = true;
                j = i;
                break;  
            }
                
            if(haystack[i] == needle[j])
                ++j;
        }
        if(!bIsMatch)
            return -1;
        else
        {
            return j+1-size2;
        }
        
    }
};