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

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

题目链接
代码随想录

分析

这道题就是为 KMP 算法量身定做的一道练习题。
KMP 的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。
所以如何记录已经匹配的文本内容，是 KMP 的重点，也是 next 数组肩负的重任。为什么叫 next，我们后面再说
next 数组就是一个前缀表（prefix table）。
这里我们理清一个概念，什么是前缀，什么是后缀

为什么要使用前缀表

为啥就能告诉我们 上次匹配的位置，并跳过去呢？
这就是前缀表，那为啥就能告诉我们 上次匹配的位置，并跳过去呢？
回顾一下，刚刚匹配的过程在下标 5 的地方遇到不匹配，模式串是指向 f，如图：
500
然后就找到了下标 2，指向 b，继续匹配：如图：
500
以下这句话，对于理解为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配 非常重要！
下标 5 之前这部分的字符串（也就是字符串 aabaa）的最长相等的前缀 和 后缀字符串是 子字符串 aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串（索引为 4）的后面，那么我们找到与其相同的前缀的后面（索引为 2）重新匹配就可以了。因为此时索引 0-2 这一段跟索引 3-4 这一段的元素都是一一对应的，所以我们不需要让指针回退到 0，然后再重新过一遍索引为 0，1 的元素，直接让指针到 2，然后继续往后即可，如果索引 2 跟索引 5 的元素相等（目前是不相等的，我们假设），那么索引 5 此时的前缀表的值就是 3。
所以前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。
这一点对于帮助我们理解后面计算 next 数组的过程和使用 next 数组进行匹配的过程非常重要

使用前缀表还是使用前缀表统一减一之后的结果

这并不涉及到 KMP 的原理，而是具体实现，next 数组既可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为 -1）。
虽然 代码随想录 中推崇使用前缀表统一减一之后的结果进行计算，但是直接使用前缀表更容易理解，而且代码也没有变得更复杂，因此为了快速解决这道算法题，我们这里直接使用前缀表作为 next 数组。

计算 next 数组 - 核心章节

我们直接看 next 数组怎么计算？

public int[] next(char[] chars){
    int[] next = new int[chars.length];
    // 这里因为是计算一个字符串的前缀，因此，没有必要计算[0,0]这个子串的前缀，直接让next[0] 为0即可
    int j=0;
    next[0]=0;
    // 然后从1开始，计算1的前缀
    for(int i=1;i<chars.length;i++){
        while(j>0 && chars[i]!=chars[j]){
            j = next[j-1];
        }
        if(chars[j]==chars[i]){
            j++;
        }
        next[i]=j;
    }
    return next;
}

如何理解这个代码呢？很简单
先从一个最简单的场景学起，就是如果一个字符串是这样的 "abcdabce"，那么如何计算其 next 数组呢？
根据这个算法，一开始的时候，j 将一直是 0，因为没有条件让 s[i] 等于 s[j],然后直到出现第一个 i，满足 s[i] 与 s[j] 相等，j 才会累加，而累加之后的 j 刚好就是 next[i] 的值，然后 i 也会继续往后移动一位，然后继续对比新的 i 和新的 j 指向的值。如果移动之后， s[i] 跟 s[j] 继续相等，j 的值就会继续累加，比如 s[i]（i=4）为 a,s[j] 也为 a，next[4] 就等于 1，表示 i=4 的时候，最长的相等的前后缀的长度是 1，然后 i 和 j 一直一起累加，i=5,的时候 next[5] 等于 2，i=6,的时候 next[6] 等于 3。
如果移动之后， s[i] 跟 s[j] 不相等，那么 j 就需要回退，回到什么地方呢？得回退到，s[0,...j-1] 与 s[i-1-j,...i-1] 这一段相等才可以，因为这样我们才能继续对比 s[j] 和 s[i]，此时 s[j] 和 s[i] 相等，那么 next[i] 就是 j+1，然后继续往后同时移动 i 和 j，即上面那一步，如果不相等，那 j 就只能继续回退了 。
那如何回退才能实现 s[0,...j-1] 与 s[i-1-j,...i-1] 这一段相等呢？
答案是使用 next 数组。使用方式是 j = next[j-1];，即让 next 数组指导 j 进行跳跃，
为什么 j = next[j-1]; 之后，s[0,...j-1] 与 s[i-1-j,...i-1] 相等？ 这是怎么保证的呢？
我们从回退之前看起，首先 j 回退之前， s[i] 跟 s[j] 不想等，可以侧面证明 s[i–1] 跟 s[j–1] 相等,如果 next[j–1] 这个位置的 next 数组的值即最长相等前后缀不为 0，那么假设最长相等前后缀长度是 y，那么 s[y-1] 肯定跟 s[j–1] 相等，即与 s[i–1] 相等，以此类推，s[0,..y-1] 和 s[j-1-y-1,...j-1] 相等，也就是说，指针退到 j 退到 y 之后，从 0 到 y 这段前缀，与 i 前面的长度为 y 的前缀，是相同的，如果此时 s[y] 等于 s[i]，那么 next[i] 就等于 y+1。
这一段推导，其实跟 28. 找出字符串中第一个匹配项的下标#为什么要使用前缀表 中的图描述的是一样的信息。

单独看 next 数组，假设 next[x] 的值是 y，其实就代表着 s[0,..y-1] 和 s[x-j-1,...x] 这两个范围的元素一一对应，当我们用 x=next[x] 进行指针跳转的时候，我们会发现，跳转前后，前面的元素 y 个元素是相同的，这就是 next 神奇的地方。

这里面有一个概念上的转变，j 是前缀的长度，同时也是下一次回退的地址，j 是最大相同的前缀长度。

其实 KMP 的 next 数组就像一个跳跃指南：告诉你：如果当前长度 j 失败了，你可以放心退回到长度 next[j-1]，因为：next[j-1] 位置前的字符和你原来 j 位置前的字符是一模一样的。只是前缀的长度变短了而已。所以这也是为什么前缀表叫 next 的原因。

使用 next 数组

使用前缀表的方式其实跟计算前缀表中的逻辑是类似的，
不过需要注意的是此时因为一个指针指向文本串，一个指向模式串，所以两个指针都是从 0 开始
此外，如果模式串的指针越界了，就到了该返回的时候了。

解题

最终答案，不统一减一版：

public int strStr(String haystack, String needle) {
    char[] sourceChar = haystack.toCharArray();
    char[] targetChar = needle.toCharArray();
    int[] next = next(targetChar);
    // 这里需要两个数组都从0开始匹配
    int i=0,j=0;
    for(;i<sourceChar.length;i++){
        while(j>0 && sourceChar[i]!=targetChar[j]){
            j = next[j-1];
        }
        if(sourceChar[i]==targetChar[j]){
            j++;
        }
        // j 是下标，只有超过了最大下标，到了 targetChar.length 才能保证所有字符都存在于sourceChar中
        if(j == targetChar.length){
            // i此时还没有+1，需要+1才能减去长度j
            return i+1-j;
        }
    }
    return -1;
}

public int[] next(char[] chars){
    int[] next = new int[chars.length];
    // 这里因为是计算一个字符串的前缀，因此，没有必要计算[0,0]这个子串的前缀，直接让next[0] 为0即可
    int j=0;
    next[0]=0;
    // 然后从1开始，计算1的前缀
    for(int i=1;i<chars.length;i++){
        while(j>0 && chars[i]!=chars[j]){
            j = next[j-1];
        }
        if(chars[j]==chars[i]){
            j++;
        }
        next[i]=j;
    }
    return next;
}

相关题

这个算法，跟 C++ 的 algorithm 包中的 search 方法可能有点关系。
实际上不是，
459. 重复的子字符串