题目描述

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

代码实现

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
//28. 找出字符串中第一个匹配项的下标
public class FindTheIndexOfTheFirstOccurrenceInAString28 {
	public static void main(String[] args){
		System.out.println(new Solution().strStr("aabaabaafa", "aabaaf"));//3
	}
}
class Solution {
    public int strStr(String haystack, String needle) {
    	if (needle.length() == 0) return 0;
    	int[] next = new int[needle.length()];
    	getNext(needle, next);

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

    		if (haystack.charAt(i) == needle.charAt(j)) j++;

    		if (j == needle.length()) return i - needle.length() + 1;
    	}
    	return -1;
    }
    public void getNext(String s ,int[] next) {
    	
    	next[0] = 0;
    	int j = 0;

    	for (int i = 1; i < s.length(); i++) {
    		//下面这个while我还没有理解透彻，但是能写出来
    		while(j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];
    		if (s.charAt(i) == s.charAt(j)) j++;
    		next[i] = j;
    	}
    }
}

个人总结

KMP

前后缀

==前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。==

==后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。==

为什么跳前缀表哪里？

image-20230402160635688

图中的加粗黑字对于理解为什么f不对付跳到2那个地方的B有很大的帮助。

整个流程的理解

image-20230402162838624

前缀表：相同前后缀的强度（<= 当前）

我们这里的实现

  1. 是 KMP
  2. 同时 next数组直接使用前缀表

我觉得这个处理是很好的一个解决途径。

我的困惑

==那个求 next()哪里的while()跳回next数组的上一个。==