特殊

KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。 KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

最常见的题型就是去查找一个主串中是否有模式串的场景.

28. 找出字符串中第一个匹配项的下标 (opens new window)

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1:

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2:

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

题解：

KMP算法的详解: 帮你把KMP算法学个通透！（理论篇） (opens new window)

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
    if (needle.length === 0) return 0;

    const getNext = (needle) => {
        const next = []
        // j是前缀串的尾部,i是后缀串的尾部,由于单字母的时候一定不存在最长公共前后缀(因为前缀串不能包含最后字母,后缀串不能包含开头字母),所以i从1开始
        // j始终做的事情是:保证前缀串(0-j)和后缀串(?-i)是一致的,由于是从最小长度2开始比较,所以不用担心后缀串开头在哪的问题,一旦有值不一致了,j就立马回退到前缀表的上一次位置再比较,如此往复
        let j = 0
        next.push(j)

        for (let i = 1; i < needle.length; i++) {
            /**
            1. 为什么用while,因为前退的过程不是一次结束的如果匹配不到一样的字母,就需要一直前退,直到匹配了或者到0位为止
            2. j最后所在的下标位置也等于是i所在位置的前缀表的值,所以可以用next[j-1]回退
             */
            while (j > 0 && needle[i] !== needle[j]) {
                j = next[j - 1]
            }

            // 如果是回退到相等值或者本来就是相等了,说明当前ij的位置,是最长公共前后缀串,但是j现在的位置,是之前的前缀表的值,举例:aabaa,j=0,i=3的情况下,二者相等,此时的最长公共子串就是"a",但是next[j]是0,所以此时需要++,这里先j++,用来赋值,i的++在循环中自我进行
            if (needle[i] === needle[j]) {
                j++
            }

            // 这里j如果在第一位且和当前i值不等,那么就是0,比如aab
            // 这里等于next[i] = j
            next.push(j)
        }

        return next
    }

    let next = getNext(needle);

    // 正式开始匹配,这里就不能i是1了,因为要从头开始匹配,j代表的还是前缀串尾部
    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++
        }

        // 如果匹配完整个needle了,则结束,注意,j会多一位,因为可能++过,此时i在最后的位置
        if (j === needle.length) {
            return i - needle.length + 1
        }

    }
    return -1
};

459. 重复的子字符串 (opens new window)

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

题解：

/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function (s) {

    // // 重复一遍s,去掉头尾,再匹配原串
    // let ss = `${s}${s}`
    // ss = ss.slice(1,ss.length-1)
    // return ss.includes(s)

    const getNext = (s) => {
        const next = []
        let j = 0
        next.push(j)


        for (let i = 1; i <= s.length - 1; i++) {
            while (j > 0 && s[i] !== s[j]) {
                j = next[j - 1]
            }

            if (s[i] === s[j]) {
                j++
            }

            next.push(j)
        }
        return next

    }

    let next = getNext(s)

    // next数组最后一位就是去掉公共字符串的长度,比如abababab,公共串长度肯定就是6(ababab),那么数组长度减去这个公共长度,也就是ab的长度2,如果正好能被总长度整除,那就是有公共子串,除不尽则代表没有

    return next[s.length - 1] !== 0 && s.length % (s.length - next[s.length - 1]) === 0


};