找出字符串中第一个匹配项的下标 | LeetCode-28 | KMP算法 | next数组 | Java

KMP算法练习题

---

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

---

1.题目描述

给你两个字符串 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 。

提示：

• $1 <= haystack.length, needle.length <= 10^4$
• haystack 和 needle 仅由小写英文字符组成

2.题解

2.1 暴力解法

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;// 如果 needle 是空字符串，返回 0，根据题目要求

        // 遍历 haystack，从索引 0 到 haystack.length() - needle.length()
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            int j = 0;
            // 检查当前子串是否与 needle 匹配
            while (j < needle.length() && haystack.charAt(i + j) == needle.charAt(j)) {
                j++;
            }
            
            if (j == needle.length()) {// 如果 j 达到 needle.length()，说明完全匹配
                return i;
            }
        }
        
        return -1;// 如果没有找到匹配的子串，返回 -1
    }
}

2.2 KMP算法

2.2.1 KMP写法1（不减1）

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return -1; // 如果 needle 是空字符串，返回 0，根据题目要求

        int[] next = getNext(needle);// 生成 needle 的前缀函数数组

        int j = 0; // 匹配指针，用于遍历 needle
        for (int i = 0; i < haystack.length(); i++) {
            // 当前字符不匹配时，根据前缀函数回退 j
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) j = next[j - 1];
            // 如果字符匹配，增加 j
            if (haystack.charAt(i) == needle.charAt(j)) j++;
            // 完全匹配，返回起始位置
            if (j == needle.length()) return i - needle.length() + 1;
        }
        // 如果没有找到匹配，返回 -1
        return -1;
    }

    // 生成前缀函数数组
    public int[] getNext(String s) {
        int n = s.length();
        int[] next = new int[n];
        int j = 0; // 前缀指针

        next[0] = 0; // 第一个字符的前缀长度为0

        for (int i = 1; i < n; i++) {
            // 当前字符不匹配时，回退前缀指针 j
            while (j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];
            // 如果字符匹配，前缀长度增加
            if (s.charAt(i) == s.charAt(j)) j++;
            // 记录前缀长度到 next 数组
            next[i] = j;
        }
        return next;
    }
}

2.2.2 KMP写法2（减1）

class Solution {
    public int strStr(String haystack, String needle) {
        // 如果 needle 是空字符串，返回 -1（根据题目要求）
        if (needle.length() == 0) return -1;

        // 生成 needle 的前缀函数数组，用于 KMP 算法
        int[] next = getNext(needle);
        int j = -1;// 匹配指针 j，用于遍历 needle。初始值为 -1，表示还没有匹配任何字符

        // 遍历 haystack 中的每个字符
        for (int i = 0; i < haystack.length(); i++) {
            // 当前字符不匹配时，根据前缀函数回退 j，直到找到一个可匹配的前缀位置或 j 变为 -1
            while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) j = next[j];

            // 如果当前字符匹配，增加 j 以匹配 needle 的下一个字符
            if (haystack.charAt(i) == needle.charAt(j + 1)) j++;

            // 如果 j 达到了 needle 的最后一个字符的位置，表示找到了匹配的子串
            if (j == needle.length() - 1) return i - needle.length() + 1;     
        }
        return -1;// 如果没有找到匹配的子串，返回 -1
    }

    // 生成前缀函数数组 next，用于 KMP 算法
    public int[] getNext(String s) {
        int n = s.length();
        int[] next = new int[n];
        int j = -1;// 前缀指针 j，初始值为 -1，表示还没有匹配任何前缀
        next[0] = -1;// next[0] 初始化为 -1，表示第一个字符没有前缀

        // 从第二个字符开始，遍历整个字符串 s
        for (int i = 1; i < n; i++) {
            // 当前字符不匹配时，回退前缀指针 j，直到找到一个可匹配的前缀位置或 j 变为 -1
            while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) j = next[j];

            if (s.charAt(i) == s.charAt(j + 1)) j++;// 如果当前字符匹配，增加 j 以匹配下一个字符
            next[i] = j; // 记录前缀长度到 next 数组
        }
        return next;
    }
}

2.3 KMP算法改进

• nextval 数组是对 next 数组的进一步优化，主要用于加快失配后的回溯过程。nextval 数组在失配时可以避免一些不必要的匹配操作，从而提高算法的效率。

2.3.1 写法1（不减1）

// 生成优化后的前缀函数数组 nextval
public int[] getNextval(String s) {
    int n = s.length();
    int[] nextval = new int[n];
    int j = 0; // 前缀指针

    nextval[0] = -1; // 第一个字符的前缀长度设为 -1

    for (int i = 1; i < n; i++) {
        // 当前字符不匹配时，回退前缀指针 j
        while (j > 0 && s.charAt(i) != s.charAt(j + 1)) {
            j = nextval[j]; // 根据 nextval 数组回退
        }
        // 如果字符匹配，前缀长度增加
        if (s.charAt(i) == s.charAt(j + 1)) {
            j++;
        }
        // 记录当前字符的前缀长度到 nextval 数组
        nextval[i] = j; // 当前字符的前缀长度
    }
    return nextval;
}

2.3.2 写法2（减1）

public int[] getNextval(String s) {
    int n = s.length();
    int[] nextval = new int[n];
    
    int j = -1; // 前缀指针
    nextval[0] = -1; // 初始化第一个字符的 nextval 为 -1
    
    for (int i = 1; i < n; i++) {
        // 当当前字符不匹配时，回退前缀指针 j
        while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) j = nextval[j]; 
        
        // 如果字符匹配，前缀长度加一
        if (s.charAt(i) == s.charAt(j + 1)) j++;

        // 若失配时，当前字符与 nextval[j] 指向的字符相同，则使用 nextval[j]
        if (i < n - 1 && s.charAt(i + 1) == s.charAt(j + 1)) 
            nextval[i] = nextval[j];
        else
            nextval[i] = j;

    }
    
    return nextval;
}