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

【题目描述】

给你两个字符串 ​​haystack​​ 和 ​​needle​​ ，请你在 ​​haystack​​ 字符串中找出 ​​needle​​ 字符串的第一个匹配项的下标（下标从 0 开始）。如果 ​​needle​​ 不是 ​​haystack​​ 的一部分，则返回  ​​-1​​ 。

​​https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/​​

【示例】

【代码】admin

思路: 基于内部API

package com.company;
import java.util.*;

// 2023-2-19
class Solution {
public int strStr(String haystack, String needle) {
return haystack.indexOf(needle);
    }
}

public class Test {
public static void main(String[] args) {
new Solution().strStr( "sadbutsad", "sad");  // 输出: 0
new Solution().strStr( "leetcode", "leeto"); // 输出: -1
    }
}

【代码】​​基于KMP​​

package com.company;
import java.util.*;

// 2023-2-19
class Solution {
// 基于KMP算法
public int strStr(String haystack, String needle) {
int m = needle.length();
if (m == 0) return 0;
// 开辟前缀表的存储数组空间
int[] next = new int[m];
// 初始化
this.getNext(needle, next);

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

public void getNext(String needle, int[] next) {
// 初始化
int j = 0;
next[0] = 0;

for (int i = 1; i < needle.length(); i++){
// 匹配不相等的情况, 回退到前一个数组
while (j > 0 && needle.charAt(j) != needle.charAt(i)){
j = next[j - 1];
            }
// 匹配相等的情况
if (needle.charAt(j) == needle.charAt(i)){
j++;
            }
// 更新next数组
next[i] = j;
        }
    }
}

public class Test {
public static void main(String[] args) {
new Solution().strStr( "sadbutsad", "sad");  // 输出: 0
new Solution().strStr( "leetcode", "leeto"); // 输出: -1
    }
}