KMP算法基礎(chǔ)

• 主要應(yīng)用：在字符串匹配上。
• 主要思想：匹配過程中，當(dāng)出現(xiàn)不匹配的字符時，可以知道一部分之前已經(jīng)匹配的文本內(nèi)容，可以利用這些信息避免從頭再去做匹配了。
• 什么是前綴：是指不包含最后一個字符的所有以第一個字符開頭的連續(xù)子串。比如字符串"aab"的前綴有：a，aa。
• 什么是后綴：是指不包含第一個字符的所有以最后一個字符結(jié)尾的連續(xù)子串。
  比如字符串"aab"的后綴有：b，ab。
• 什么是最長相同前后綴：字符串"aab"的前、后綴不存在相同的字符串，所以最長相同前后綴長度為0。
• 什么是前綴表：字符串從索引 i = 0 開始，統(tǒng)計 0 ~ i (包括i) 的字符串中最長相同前后綴組成的數(shù)組。

舉例：字符串 "aabaaf"
詳細(xì)過程：
i = 0, 字符串為 a，最長相同前后綴長度為 0
i = 1, 字符串為 aa，前綴：a，后綴：a，存在1個相同的前后綴，則最長相同前后綴長度為 1
i = 2, 字符串為 aab，前綴：a,aa，后綴：b,ab，不存在相同的前后綴，則最長相同前后綴長度為 0
i = 3, 字符串為 aaba，前綴：a,aa,aab，后綴：a,ba,aba，存在 1 個相同的前后綴 a，則最長相同前后綴長度為 1
i = 4, 字符串為 aabaa，前綴：a,aa,aab,aaba，后綴：a,aa,baa,abaa，存在 2 個相同的前后綴 a 和 aa，則最長相同前后綴為 2
i = 5, 字符串為 aabaaf，前綴：a,aa,aab,aaba,aabaa，后綴：f,af,aaf,baaf,abaaf，存在 0 個相同的前后綴，則最長相同前后綴為 0
所以其前綴表為 [0, 1, 0, 1, 2, 0]

• 前綴表的作用：

舉例：文本串"aabaabaafa"，模式串"aabaaf"

image.png

如圖，當(dāng)匹配到下標(biāo) i = 5時，當(dāng)出現(xiàn) b 和 f 不匹配的字符時，下一步可以直接跳到下標(biāo)為 2 的位置繼續(xù)匹配。
至于為什么是跳轉(zhuǎn)到下標(biāo)為2的位置，是根據(jù)前綴表來的
下標(biāo)5之前這部分的字符串（也就是字符串a(chǎn)abaa）的最長相等的前綴 和 后綴字符串是 子字符串a(chǎn)a ，因為找到了最長相等的前綴和后綴，匹配失敗的位置是后綴子串的后面，那么我們找到與其相同的前綴的后面重新匹配就可以了。

• 如何構(gòu)建前綴表
  實現(xiàn)一

1. 初始化兩個指針 i = 0, j = -1，數(shù)組 next = [j];
   其中 i 指向后綴末尾位置，j 指向前綴末尾位置;
   比如i = 2，指向字符b，已經(jīng)匹配過的字符串為 aab，此時 i 指向后綴末尾即字符b，j 指向前綴末尾即字符a；
2. 處理前后綴不相同的情況
3. 處理前后綴相同的情況

28. 找出字符串中第一個匹配項的下標(biāo)

解題思路

var strStr = function(haystack, needle) {
    if (needle.length === 0) {
        return 0;
    }
    // 初始化j=-1
    let j = -1;
    let next = []
    next.push(j);
    // 遍歷模式字符串
    for (let i = 1; i < needle.length; i++) {
        // 前后綴不相同
        while(j >= 0 && needle[i] !== needle[j+1]) {
            j = next[j] // 向前回退
        }
        // 前后綴相同
        if (needle[i] === needle[j+1]) {
            j++
        }
        next.push(j)
    }
    j = -1;
    for (let i = 0; i < haystack.length; i++) {
        while(j >= 0 && haystack[i] !== needle[j+1]) {
            j = next[j]
        }
        if (haystack[i] === needle[j+1]) {
            j++
        }
        if (j == (needle.length - 1) ) { // 文本串s里出現(xiàn)了模式串t
            return (i - needle.length + 1);
        }
    }
    return -1
};