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

[HealUP]

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

思路：使用KMP算法，一定要构造next数组（即前缀表）

• next数组，就是以模式串中各个字符串结尾的最长相等前后缀的集合

KMP算法 1.构造next数组（和模式串大小一致） 2.模式串用next数组匹配文本串

那怎么构造next数组呢，思路：

1.初始化 2.处理前后缀不相同的情况 3.处理前后缀相同的情况

注：以下统称haystack为文本串, needle为模式串

时间复杂度：其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。时间复杂度是O(n+m)。

法一：前缀表不减一

class Solution {
    public int strStr(String haystack, String needle) {
        //前后缀不减一的实现方式
        //边界判断
        if (needle.length() == 0) return 0;
        int[] next = new int[needle.length()];//创建一个和模式串一样大的next数组
        getNext(next, needle);//得到填充好的next数组

        //使用next数组来做匹配 在文本串里找是否出现过模式串
        //定义两个下标,j指向模式串起始位置，i指向文本串起始位置
        int j = 0;//和next数组中j的起始位置对应
        for (int i = 0; i < haystack.length(); i++) {
            //不匹配的情况
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) {//模式串的j>0,=0的话，下面的next就是next[-1]就出界了
                //找到回退的位置,即改变前缀末尾的位置j
                j = next[j - 1];
            }
            if (needle.charAt(j) == haystack.charAt(i)) {
                j++;//前缀末尾后移
            }
            //判断在文本串s里出现了模式串t呢，如果j指向了模式串t的末尾，那么就说明模式串t完全匹配文本串s里的某个子串了
            if (j == needle.length()) {
                return i - needle.length() + 1;//因为返回的是下标，所以要+1；比如：长度是3，其最大下标就是2，数组下标从0开始的
            }
        }
        //跳出循环了，说明找不到匹配的模式串的了
        return -1;
    }

    //构造next数组
    /*
    思路：1.初始化
         2.处理前后缀不相同的情况
         3.处理前后缀相同的情况
    */
    private void getNext(int[] next, String s) {
        //定义两个指针i和j，j指向前缀末尾位置，i指向后缀末尾位置
        //next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是j）
        //next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度
        int j = 0;
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {//从1开始，因为0的位置肯定是0的，只有一个字符的时候，不存在相等的前后缀
            //不相等前后缀的情况，回退  这里用while 是因为只要不相等就一致回退到相等或者到索引为1的位置
            while (j > 0 && s.charAt(j) != s.charAt(i)) {
                //改变前缀的末尾
                j = next[j - 1];//不匹配字符的上一个位置
            }
            // 找到相同的前后缀
            if (s.charAt(j) == s.charAt(i)) {
                j++;//索引为i的位置的值加1
                next[i] = j;//更新当前下标为i的next数组
                }
            }
        }
}