2018-06-08 28. Implement strStr(

题意：给两个串s1,s2，找到s2在s1中第一次出现的位置，若s2不在s1中返回-1.
解题思路：子串匹配算法，假设n = s1.size(), m = s2.size().
暴力匹配算法时间复杂度O((n-m+1)*m)，太耗时。
KMP算法时间复杂度O(m+n).
KMP算法详情：
首先计算给出的模式串的next数组，该数组存储模式串的信息，例如第K个值表示的是模式串到该位最长前缀==最长后缀的长度，也是在两个字符串匹配的时候，该位的下一位出现不匹配时，接下来应该拿模式串的第几位与待找串的当前位进行比较。
求next数组的代码为：

void makeNext(string s, vector<int>& next){
        next[0] = 0;
        for(int k = 0, q = 1; q < next.size(); q++){
            while(k > 0 && s[q] != s[k])
                k = next[k-1];
            if(s[q] == s[k])
                k++;
            next[q] = k;
        }
    }

得到了next数组，主串与模式串的匹配代码为：

    int kmpstr(string s1, string s2){
        vector<int> next(s2.size());
        makeNext(s2, next);
        for(int i = 0, k = 0; i < s1.size(); i++){
            while(k > 0 && s1[i] != s2[k])
                k = next[k-1];
            if(s1[i] == s2[k])
                k++;
            if(k == s2.size())
                return i - k + 1;
        }
        return -1;
    }

假如一开始不懂，不要悲伤不要哭泣，先写10遍再说。
今天不懂写十遍，明天不懂再写十遍，反复理解和默写，直到完全掌握。