28. 找出字符串中第一个匹配项的下标(简单)twice

Posted on Edited on In Views:

1，问题描述

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

难度：简单

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

示例 1：

1
2
3
4
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

1
2
3
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

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

2，初步思考

​ 本身这道题目没什么难度，主要是与其相关的KMP算法需要掌握一下

​ 时间复杂度O(n*m)

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
public class _28找出字符串中第一个匹配项的下标 {

    // 直接应用kmp算法
    public int strStr(String haystack, String needle) {
        int[] next = getNext(needle);
        int i = 0, j = 0;
        while (i < haystack.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {// 匹配成功,升级
                i++;
                j++;
            } else {
                if (j == 0) {
                    i++;
                } else {
                    j = next[j - 1];// 要与前一个数据的next值比较
                }
            }
            if (j == needle.length()) {
                return i - needle.length();// 起始坐标
            }
        }
        return -1;
    }

    // 获取kmp next的数组
    private int[] getNext(String needle) {
        char[] charArray = needle.toCharArray();
        int n = charArray.length;
        int[] next = new int[n];
        int idx = 1;
        int prefix_len = 0;
        while (idx < n) {
            if (charArray[prefix_len] == charArray[idx]) {
                prefix_len++;
                next[idx] = prefix_len;
                idx++;
            } else {// 不相等
                if (prefix_len == 0) {
                    next[idx] = 0;
                    idx++;
                } else {
                    prefix_len = next[prefix_len - 1];
                }
            }
        }
        return next;
    }

    private int[] getNext_option(String needle) {
        char[] charArray = needle.toCharArray();
        int n = charArray.length;
        int[] next = new int[n];
        int i = 1;// 第一个肯定是0
        int len = 0;// 前缀长度，这个比较难理解
        while (i < n) {
            if (charArray[i] == charArray[len]) {
                next[i++] = ++len;
            } else {// 不相等
                if (len == 0) {
                    i++;
                } else {
                    len = next[len - 1];
                }
            }
        }
        return next;
    }

    public static void main(String[] args) {
        _28找出字符串中第一个匹配项的下标 findStr = new _28找出字符串中第一个匹配项的下标();
//        String haystack = "mississippi";
//        String needle = "issip";
        String haystack = "aabaaabaaac";
        String needle = "aabaaac";
//        String haystack = "leetcode";
//        String needle = "leeto";
        int index = findStr.strStr(haystack, needle);
        System.out.println(index);
    }
}
/**
 * aaaaaa
 * [0,1,2,3,4,5]
 * aaabaaaac
 * [0,1,2,0,0,1,2,0,0]
 * <p>
 * aabaaac
 * [0,1,0,0,1]
 * <p>
 * abacabab
 * [0,0,1,0,1,2,3,0]
 */