代码随想录算法训练营第八天|LeetCode28，459

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

题目链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

//kmp算法
class Solution {
public:
    //kmp算法
    //写一个构建next的数组
    void getNext(int *next, const string &s){
        //构建next数组要知道：next数组的每个值是每个模式子串的最长相等前后缀值
        //j代表每个子串的前缀末尾以及最长相等前后缀值
        int j = 0;
        //初始化
        next[0] = 0;
        //i代表每个子串的后缀末尾
        //因为一般两个元素才算前后缀，所以让 i = 1；
        //遍历每个子串，记录每个子串的最长相等前后缀
        //比如aabaaf，就是求aa的最长相等前后缀，aab的最长相等前后缀，aaba的最长相等前后缀。。依次类推
        for(int i = 1; i < s.size(); i++){
            //前后缀不匹配时，当s[i]不等于s[j]，j要通过next[j-1]的值跳回 
            while(s[i] != s[j] && j > 0){
                j = next[j-1];
            }
            //前后缀匹配时，当s[i]等于s[j]
            if(s[i] == s[j]){
                j++;
                //next[i] = j; error 不能写在if里，加入某子串无匹配，next[i]该填入何值？
            }
            next[i] = j;
        }

    }

    //模式串和给定串进行匹配
    int strStr(string haystack, string needle){
        if(needle.size() == 0){
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        //假设模式串aabaaf，给定串aabaabaaf
        int j = 0;
        for(int i = 0; i < haystack.size(); i++){
            while(haystack[i] != needle[j] && j > 0){
                j = next[j-1];
            }
            if(haystack[i] == needle[j]){
                j++;
            }
            //为什么判断条件不是j == needle.size()-1。因为如果模式串和给定串的最后一个字符匹配上，j还要++
            if(j == needle.size()){
                return(i - needle.size() + 1);
            }
        }
        return -1;

    }
};

视频讲解链接：https://www.bilibili.com/video/BV1PD4y1o7nd/?spm_id_from=pageDriver&vd_source=8d6cce160628d93add1e5fa9299f622d

文章讲解链接：https://programmercarl.com/0028.实现strStr.html#其他语言版本

LeetCode 459 重复的子字符串

题目链接：https://leetcode.cn/problems/repeated-substring-pattern/description/

//需要转换思路了，搁这三过家门而不入呢。使用next的思路倒没错，但是repeatedSubstringPattern函数体里写得有问题，需要重新想想，还是kmp掌握得不熟练
class Solution {
public:
    //检查一个字符串是否一个子串多次构成
    //联想kmp算法，对这个字符串求next数组

    void getNext (int *next, const string &s){
        //初始化
        next[0] = 0;
        //j指向子串的前缀的末尾以及最长相等前后缀值
        int j = 0;
        //i指向子串的后缀末尾，所以i从1开始
        //遍历每个子串
        for(int i = 1; i < s.size(); i++){
            //当前后缀不相等时
            while(j > 0 && s[i] != s[j]){
                j = next[j-1];
            }
            //当前后缀相等时
            if(s[i] == s[j]){
                j++;
            }
            next[i] = j;
        }
        
    }

    bool repeatedSubstringPattern(string s) {
        int next[s.size()];
        getNext(next, s);
        if(s.size() == 2 && s[0] == s[1]) return true;
        int i;
        for(i = 0; i < s.size(); i++){
            if(next[i] == 1) break;
        }
        if(i == s.size() || i == s.size()-1) return false;
        int counts = i;
	    if((s.size()-counts)/counts < 0 || (s.size()-counts)%counts != 0) return false;
        for(; i < s.size() -1 ; i++){
            if(next[i] + 1 != next[i+1]) return false;

        }
        return true;
        
            
    }

};

视频讲解链接：https://www.bilibili.com/video/BV1cg41127fw/?spm_id_from=333.788&vd_source=8d6cce160628d93add1e5fa9299f622d

文章讲解链接：https://programmercarl.com/0459.重复的子字符串.html#kmp

class Solution {
public:
    //检查一个字符串是否一个子串多次构成
    //联想kmp算法，对这个字符串求next数组
    void getNext (int *next, const string &s){
        //初始化
        next[0] = 0;
        //j指向子串的前缀的末尾以及最长相等前后缀值
        int j = 0;
        //i指向子串的后缀末尾，所以i从1开始
        //遍历每个子串
        for(int i = 1; i < s.size(); i++){
            //当前后缀不相等时
            while(j > 0 && s[i] != s[j]){
                j = next[j-1];
            }
            //当前后缀相等时
            if(s[i] == s[j]){
                j++;
            }
            next[i] = j;
        }
        
    }
    bool repeatedSubstringPattern(string s) {
        if(s.size() == 0) return false;
        int next[s.size()];
        getNext(next, s);
        //
        int i = s.size();
        if(next[i - 1] != 0 && i % (i - next[i - 1]) == 0){
            return true;
        }
        return false;

    }
};