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

1.题目

2.知识点

注1：涉及到两个字符串匹配的问题的时候，要考虑KMP算法
注2：i<=hLength-nLength，必须取等号
. 比如都是一个字母的长度时候hLength-nLength=0，i<0说明取负数了
注3：else return -1:注释掉的原理当 i = 0 时，我们获取了 “hello” 的子串 “he” 与 “ll” 进行比较，不匹配，但由于 return -1 在这个循环中，因此直接返回 -1，导致没有进行后续的匹配尝试。

3.代码实现

方法1：

class Solution {
    public int strStr(String haystack, String needle) {

        int hLength=haystack.length();
        int nLength=needle.length();
        //遍历主串，尝试在主串的每个位置匹配子串
        for(int i=0;i<=hLength-nLength;i++)
        {
            if(haystack.substring(i,i+nLength).equals(needle))
            {
                return i;
            }
         //  else
         //return -1;
        }
        return -1;
    }
}

方法2：kmp(未理解完…

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) return 0; // 如果 needle 为空，则返回 0

        int[] lps = computeLPSArray(needle); // 构建部分匹配表

        int i = 0; // 主串指针
        int j = 0; // 模式串指针
        while (i < haystack.length()) {
            if (needle.charAt(j) == haystack.charAt(i)) { // 如果当前字符匹配
                i++;
                j++;
            }
            if (j == needle.length()) { // 如果找到了完整匹配的模式串
                return i - j; // 返回匹配位置的起始索引
            } else if (i < haystack.length() && needle.charAt(j) != haystack.charAt(i)) { // 如果当前字符不匹配
                if (j != 0)
                    j = lps[j - 1]; // 通过部分匹配表跳转到可能的匹配位置
                else
                    i++; // 移动主串指针
            }
        }
        return -1; // 没有找到匹配位置，返回 -1
    }

    // 构建部分匹配表
    private int[] computeLPSArray(String pattern) {
        int m = pattern.length(); // 模式串长度
        int[] lps = new int[m]; // 部分匹配表

        int length = 0; // 已匹配的前缀长度
        int i = 1; // 当前字符指针
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(length)) { // 如果当前字符与已匹配的前缀字符匹配
                length++;
                lps[i] = length; // 更新部分匹配值
                i++;
            } else { // 如果不匹配
                if (length != 0)
                    length = lps[length - 1]; // 回溯到上一个可能的匹配位置
                else {
                    lps[i] = 0; // 无法回溯，当前字符的部分匹配值为0
                    i++; // 移动指针
                }
            }
        }
        return lps; // 返回部分匹配表
    }
}