代码随想录 字符串 test 6（KMP，超详细）

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

一 暴力:

        以主串中的每个字符为起点，每次匹配从当前主串的起点和子串的首位开始匹配：匹配成功：返回本次匹配的主串起点。匹配失败：以主串的下一个字符作为新起点，重新尝试匹配。时间复杂度为o(m*n)(m为主串长度，n为子串长度，因为每次从主串起点开始都要遍历一遍子串)

class Solution {
public:
    int strStr(string haystack, string needle) {
        for(int i = 0; i <= haystack.size() - needle.size(); i++){
            int j = i, k = 0;//j为每次主串的起点,k为子串的起点

            while(k < needle.size() && needle[k] == haystack[j]){
                j++, k++;
            }

            if(k == needle.size())
                return i;
        }
        
        return -1;
    }
};

二 KMP:

关键：通过预处理子串，记录模式串中每个位置的最长相同前缀和后缀的长度。当匹配失败时，利用这些信息跳过不必要的比较。算法分为两部分：next数组的建立以及模式串匹配的过程。

1 next数组：

        采用next数组从0开始，next数组值即当前位置子串的最长相等前后缀，如ababa，此时最后一个字符a处的最长相等前后缀为"aba"，因此他的next数组值为3，同理倒数第二个字符b的next数组值为2，整体next数组为00123，因此如果当前位置j匹配失败(第1个位置特殊讨论)，说明他前面的字符s[j-1]匹配成功，此时next[j-1]也就是匹配成功部分的最长相等前后缀大小，说明下次匹配可以直接从该前缀的下一个字符开始匹配，也就是从next[j-1]开始(大小等于序号加1)。

        创建：此时可以将前缀当作子串，后缀当作主串(无非就是匹配成功并不返回，而是赋值)设置前缀指针j和后缀指针i，起始位置next[0]=0，j从0开始，i从1开始。注意i指针始终向后移动，先判断是否相等，再为当前next[i]赋值。如果相等，说明前后缀扩大，将j后移，如果不相等，将不相等的情形视为不匹配的情况，要想知道当前位置的最大前后缀，即j位置失配时下一个要检查的位置next[j-1]，若此时相等，相等前后缀大小为next[j-1]，若不相等则一直递归(因为要找前后缀的值，而不是判断是否匹配成功)，直到相等或j=0为止。最后在本次遍历结束前将j的值赋给next[i]。

2 匹配：

        与上述类似，设置主串指针i，子串指针j，相等时两指针同时后移，不等时j一直利用next数组回退，如果j遍历到子串结尾就说明匹配成功。

3 代码：

class Solution {
public:
    void getNext(int* next, const string& needle){
        int j=0;
        next[0] = 0;

        for(int i = 1; i < needle.size(); i++){
            while(j > 0 && needle[i] != needle[j]){
                j = next[j - 1];
            }

            if(needle[i] == needle[j]){
                j++;
            }

            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if(haystack.size() == 0) return 0;

        int next[needle.size()];

        getNext(next, needle);

        int j = 0;

        for(int i = 0; i < haystack.size(); i++){
            while(j > 0 && needle[j] != haystack[i]){
                j = next[j - 1];
            }

            if(needle[j] == haystack[i]){
                j++;
            }
            
            if(j == needle.size()){
                return i - needle.size() + 1;
            }
        }

        return -1;
    }
};