[代码随想录] KMP 算法 28. 找出字符串中第一个匹配项的下标 459. 重复的子字符串

KMP 基础知识

奇乐编程学院
https://www.bilibili.com/video/BV1AY4y157yL/?spm_id_from=333.1391.0.0
代码随想录
https://www.bilibili.com/video/BV1PD4y1o7nd?spm_id_from=333.788.videopod.sections&vd_source=9e875f3cfd35b93ea904ffd5c3c157a5
一个人能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。
————KMP
（复制的B站评论）

概述：使用前缀表来代替重复比较。
kmp算法关键在于：在当前对文本串和模式串检索的过程中，若出现了不匹配，如何充分利用已经匹配的部分。
主要步骤：

1. 构建前缀表
2. 遍历字符串，利用前缀表进行更新

构建前缀表

前缀不包含尾字母，一定包含首字母的所有子串。
后缀不包含首字母，一定包含尾字母的所有字串。
在构建前缀表的时候就使用了KMP思想。

使用前缀表减少运算步骤

前面i，j都是在同一个字符串下。求重复子串的时候，
KMP算法遇到不匹配的地方，可以直接跳到上一次匹配的地方继续匹配。

28. 找出字符串中第一个匹配项的下标

就是存在问题的基础上，如果遍历过程中遇到j==needle.size();直接返回return i-needle.size()+1;
下面注释了一个双指针法，两个指针遍历两个字符串，在没接触KMP时候写的。

class Solution {
public:
    void build_next(vector<int>& next, string s){
        next[0] = 0;
        int j = 0;//前缀的末尾
        for(int i = 1; i < s.size(); i ++){ //i后缀的末尾,就是表示这个子串的结束
            while(j>0 && s[i]!=s[j]){
                j = next[j-1];
            }
            if(s[i] == s[j]){
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.empty()) return 0;
        vector<int> next(needle.size());
        build_next(next, needle);
        int j = 0;
        for(int i = 0; i < haystack.size(); i++){
            while(j>0 && haystack[i]!=needle[j]){
                j = next[j-1];
            }
            if(haystack[i] == needle[j]){
                j++;
            }
            if(j == needle.size()) return i-needle.size()+1;
        }
        return -1;
    }
};
        // for(int i=0; i < haystack.size(); i++){
        //     int left = 0;
        //     if(needle[left]==haystack[i]){
        //         int right = i+1;
        //         left++;
        //         while(left<needle.size()){
        //             if(needle[left]!=haystack[right]) break;
        //             left++;
        //             right++;
        //         }
        //         if(left == needle.size()) return i;
        //     }
        // }
        // return -1;

459. 重复的子字符串

class Solution {
public:
    void build_next(vector<int>& next, string s){
        int j = 0;
        next[0] = 0;//初始化
        for(int i = 1; i < s.size(); i++){
            while(s[i]!=s[j] && j>0){
                j = next[j-1];//跳跃到下一个要比较的地方
            }
            if(s[i]==s[j]) next[i] = ++j;
        }
    }
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        vector<int> next(n);
        build_next(next, s);
        int len = next[n-1];
        return len > 0 && n % (n - len) == 0;
    }
};