代码随想录算法训练营第第九天 | 28. 实现 strStr() 、459.重复的子字符串

28. 实现 strStr()

因为KMP算法很难，大家别奢求 一次就把kmp全理解了，大家刚学KMP一定会有各种各样的疑问，先留着，别期望立刻啃明白，第一遍了解大概思路，二刷的时候，再看KMP会 好懂很多。
或者说大家可以放弃一刷可以不看KMP，今天来回顾一下之前的算法题目就可以。
因为大家 算法能力还没到，细扣 很难的算法，会把自己绕进去，就算别人给解释，只会激发出更多的问题和疑惑。所以大家先了解大体过程，知道这么回事， 等自己有 算法基础和思维了，在看多看几遍视频，慢慢就理解了。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0028.实现strStr.html

早上看了一遍，晚上又看了一遍，理解虽然加深了，但还处于半懂状态
function getNext(t){
    let j = 0;
    const next = [0];
    for(let i=1;i<t.length;i++){

        while(j>0 && t[i]!==t[j]){
            j = next[j-1];
        }
        if (t[i]===t[j]) {
            j++;
        }
        next[i]=j;
    }
    return next;
}

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    const next = getNext(needle);
    let j = 0;
    for(let i=0;i<haystack.length;i++){
        while(j>0&&haystack[i]!==needle[j]){
            j = next[j-1];
        }
        if (haystack[i]===needle[j]){
            j++;
        }
        if(j===needle.length){
            return i - needle.length + 1; 
        }
    }
    return -1;
};

459.重复的子字符串

本题算是KMP算法的一个应用，不过 对KMP了解不够熟练的话，理解本题就难很多。
我的建议是 KMP和本题，一刷的时候 ，可以适当放过，了解怎么回事就行，二刷的时候再来硬啃
题目链接/文章讲解/视频讲解：https://programmercarl.com/0459.重复的子字符串.html

function getNext(s){
    let j =0;
    const next =[0];
    for(let i=1;i<s.length;i++){
        while(j>0&&s[i]!==s[j]){
            j = next[j-1];
        }
        if(s[i]===s[j]){
            j++;
        }
        next[i]=j;
    }
    return next;
}
/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function(s) {
    const next = getNext(s);
    let len = s.length;
    let max = next[len-1];
    if(max===0){
        return false;
    }
    if(len%(len-max) === 0){
        return true;
    }
    return false;
};

字符串总结

比较简单，大家读一遍就行
题目链接/文章讲解：https://programmercarl.com/字符串总结.html

双指针回顾

此时我们已经做过10到双指针的题目了，来一起回顾一下，大家自己也总结一下双指针的心得
文章讲解：https://programmercarl.com/双指针总结.html