代码随想录训练营Day9|KMP字符串匹配

KMP算法基础

• 主要应用：在字符串匹配上。
• 主要思想：匹配过程中，当出现不匹配的字符时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
• 什么是前缀：是指不包含最后一个字符的所有以第一个字符开头的连续子串。比如字符串"aab"的前缀有：a，aa。
• 什么是后缀：是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
  比如字符串"aab"的后缀有：b，ab。
• 什么是最长相同前后缀：字符串"aab"的前、后缀不存在相同的字符串，所以最长相同前后缀长度为0。
• 什么是前缀表：字符串从索引 i = 0 开始，统计 0 ~ i (包括i) 的字符串中最长相同前后缀组成的数组。

举例：字符串 "aabaaf"
详细过程：
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

如图，当匹配到下标 i = 5时，当出现 b 和 f 不匹配的字符时，下一步可以直接跳到下标为 2 的位置继续匹配。
至于为什么是跳转到下标为2的位置，是根据前缀表来的
下标5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了。

• 如何构建前缀表
  实现一

1. 初始化两个指针 i = 0, j = -1，数组 next = [j];
   其中 i 指向后缀末尾位置，j 指向前缀末尾位置;
   比如i = 2，指向字符b，已经匹配过的字符串为 aab，此时 i 指向后缀末尾即字符b，j 指向前缀末尾即字符a；
2. 处理前后缀不相同的情况
3. 处理前后缀相同的情况

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

解题思路

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里出现了模式串t
            return (i - needle.length + 1);
        }
    }
    return -1
};