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

🚀 相关链接

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

📜 描述

给你两个字符串 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 仅由小写英文字符组成

💭 思路

1. KMP算法

KMP算法是一种用于字符串匹配的经典算法，其核心思想是通过构建部分的匹配表（next数组），在匹配失败时能够跳过一部分字符，从而提高匹配效率。具体思路如下：

1. 构建next数组：计算模式串（needle）的next数组，next数组的每个元素表示在当前字符匹配失败时，模式串中下一个字符的位置。
2. 使用next数组进行匹配：在匹配过程中，如果当前字符匹配失败，则根据next数组的值移动模式串的位置，而不是直接移动主串的位置。

2. Sunday算法

Sunday算法是一种更高效的字符串匹配算法，其核心思想是通过对模式串和主串的字符进行比较，并根据最后一次匹配失败的位置来决定下一步的移动距离。具体思路如下：

1. 预处理偏移表：计算模式串中每个字符在模式串中的位置，并为每个字符生成一个偏移量。
2. 匹配过程中使用偏移表：在匹配失败时，根据主串中下一个字符的位置来决定模式串的移动距离。

💻 代码实现

KMP算法

public int strStr(String haystack, String needle) {
    int[] next = buildNextArr(needle);

    int i = 0, j = 0;

    while (i < haystack.length() && j < needle.length()) {
        if (haystack.charAt(i) == needle.charAt(j)) {
            i++;
            j++;
        } else if (j == 0) {
            i++;
        } else {
            j = next[j - 1];
        }
    }

    if (j == needle.length()) {
        return i - j;
    } else {
        return -1;
    }
}

private int[] buildNextArr(String pattern) {
    int len = pattern.length();
    int[] next = new int[len];
    next[0] = 0;
    for (int i = 1, j = 0; i < len; i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

Sunday算法

public int strStr(String haystack, String needle) {
    int scanIndex = 0, hayStackIndex = 0, needleIndex = 0, hayLen = haystack.length(), needleLen = needle.length();
    Map<Character, Integer> offsetMap = new HashMap<>();
    for (int i = 0; i < needleLen; i++) {
        offsetMap.put(needle.charAt(i), needle.length() - i);
    }
    while (scanIndex + needleLen <= hayLen) {
        hayStackIndex = scanIndex;
        needleIndex = 0;
        // 字符匹配时，两个指针持续向后移动
        while (hayStackIndex < hayLen && needleIndex < needleLen && haystack.charAt(hayStackIndex) == needle.charAt(needleIndex)) {
            hayStackIndex++;
            needleIndex++;
        }
        // 跳出循环时，检查情况
        if (needleIndex == needleLen) { //若模式串扫描完了，说明全匹配，返回起始index
            return scanIndex;
        } else { //否则进行偏移
            if (scanIndex + needleLen >= hayLen) { //超出边界
                return -1;
            }
            boolean flag = false;
            char nextChar = haystack.charAt(scanIndex + needleLen);
            for (int i = 0; i < needleLen; i++) { //若下一个字符存在于模式串中
                if (needle.charAt(i) == nextChar) {
                    scanIndex += offsetMap.get(nextChar);
                    flag = true;
                    break;
                }
            }
            //否则偏移量为needleLen + 1
            if (!flag) {
                scanIndex += needleLen;
            }
        }
    }
    return -1;
}