KMP算法实现字符串匹配

代码随想录 (programmercarl.com)https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

方法一：暴力循环匹配

时间复杂度：O(n*m）

// 1.暴力匹配
class Solution {
public:
    int strStr(string haystack, string needle) {
        int index = 0;
        for(auto i=haystack.begin(); i!=haystack.end(); i++){
            auto pos = i;
            auto j = needle.begin();
            while(pos != haystack.end()){
                if(*(pos++) != *(j++)){
                    break;
                }
                if(j == needle.end()){
                    return index;
                }
            }
            index++;
        }
        return -1;
    }
};

方法二：KMP匹配法

（当字符不匹配时，根据模板字符串的最长公共前后缀表next，回退至匹配位置；而不是从下一位置重新循环）详见代码注释。

时间复杂度：O(n+m)

// 2.KMP匹配
class Solution {
public:
    // 根据模板字符串needle计算公共前后缀表next
    void findNext(const string& needle, vector<int>& next ){
        // 初始化next
        int j = 0;
        next[0] = j;
        // 针对needel[0,i]的字符串：j指向前缀最后一个字符，i指向后缀最后一个字符
        for(int i=1; i<needle.size(); i++){
            // 前缀后缀不相等 -> j后退（直至找到相等前缀位置 or 初始位置0)
            while( j>0 && needle[i]!=needle[j]){
                j = next[j-1];
            }

            // 前缀后缀相等 -> i,j前进
            if(needle[i] == needle[j]){
                j++;
            }

            // 记录needle[0,i]字符串的最长公共前后缀的长度（即前缀最后一个字符指向位置j)
            next[i] = j;
        }
    }

    // KMP字符串匹配法
    int KMP(const vector<int>& next, const string& haystack, const string& needle){
        // i指向haystack,j指向needle
        int j = 0;
        for(int i=0; i<haystack.size(); i++){ 
            // 不匹配->j根据next表后退至匹配位置
            while( j>0 && haystack[i]!=needle[j]){
                j = next[j-1];
            }
            // 匹配->i,j前进
            if( haystack[i] == needle[j]){
                j++;
            }
            //
            if(j == needle.size()){
                return (i-needle.size()+1);
            }
        }
        return -1;
    }

    int strStr(string haystack, string needle) {
        vector<int> next(needle.size());
        // 计算模板字符串needle计算公共前后缀表next
        findNext(needle, next);
        // 根据next进行字符串匹配
        int res = KMP(next, haystack, needle);
        return res;
    }
};

虽然我在力扣上运行两种方法的时间差不多。