LeetCode #28：Implement Strstr(实现StrStr库函数)

题目描述

本题实际上就是实现字符串匹配的 KMP 算法。与暴力匹配算法不同，KMP 算法在匹配模式串时主串的指针不会回溯。实现 KMP 算法的关键是求 next 数组，笔者在生成 next 数组时采用了将前缀表整体左移、next[0] 赋值 -1 的策略（如模式串为aabaaf，生成的 next 数组为 {-1, 0, 1, 0, 1, 2}），这样若模式串在 j 处不匹配时就通过 j = next[j] 回溯。

class Solution {
public:
    int strStr(string haystack, string needle) {
        vector<int> next(needle.length(), 0);
        initNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j]; // 不匹配时，j回溯
            }
            if (haystack[i] == needle[j]) {
                j++; // i、j指向的元素成功匹配，同时加一
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
            // 若本轮循环上面的j++未执行到就到了循环末尾，说明指示主串的指针i须自增尝试匹配下一个元素（模式串的第一个数不匹配，或指针j回溯到索引0处后还是不匹配，即转化成了模式串的第一个数不匹配的情况）
        }

        return -1;
    }

    // 构建next数组
    void initNext(vector<int>& next, string& s) {
        next[0] = -1; // next[0]一定为-1，代表若模式串的第一个数都不匹配，那主串指针i必须+1，尝试匹配后面的元素
        if(next.size() == 1)
            return;
        
        if(next.size() == 2) {
            next[1] = 0; // next[1]只要存在，就一定为0
            return;
        }

        // 生成next[2]及以后的元素
        // 求next数组（最长公共前后缀）的过程其实就是前缀去匹配后缀的过程
        int j = 0; // j指向最长前缀的最后一个字符，同时其数值也是子串s[0...i-1]最长前缀子串的长度
        next[1] = 0;
        
        for(int i = 2; i < next.size(); i ++) { // i-1指向最长后缀的最后一个字符
            while (j > 0 && s[i - 1] != s[j]) { // 因next[0] == -1，为了防止j = next[0]的情况要限制j > 0
                j = next[j]; // 前后缀末尾不匹配时，回溯
            }
            if (s[i - 1] == s[j]) {
                j++; // 前后缀末尾成功匹配，i-1、j同时+1
            }
            next[i] = j; // 将j（前缀的长度）赋给next[i]
        }
    }
};