Leaky Cauldron
0%

KMP算法

Posted on Edited on

题目(LeetCode #28)

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

输入: haystack = “hello”, needle = “ll”
输出: 2

示例 2:

输入: haystack = “aaaaa”, needle = “bba”
输出: -1

题解

参考资料：

Java

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
public class KMP {
    public static int[] getNextTable(String needle) {
        int len = needle.length();
        int[] next = new int[len];
        next[0] = -1;
        int lp = -1, rp = 0;    // 左右指针, 即文章中的 k 和 index

        while (rp < len - 1) {
            if (lp == -1 || needle.charAt(rp) == needle.charAt(lp))
                // lp = -1 时, 左右指针均向右移动
                // 当左右指针所指元素相等时, 均向右移动
                next[++rp] = ++lp;
            else
                // 左右指针所指元素不等, 左指针移向其所指字符的对应 next 指向的位置
                lp = next[lp];
        }

        return next;
    }

    public static int getIndex(String haystack, String needle) {
        int haystackLen = haystack.length();
        int needleLen = needle.length();

        if (needleLen == 0) return 0;
        int haystackCur = 0, needleCur = 0;
        int[] next = getNextTable(needle);

        while (haystackCur < haystackLen && needleCur < needleLen) {
            if (haystack.charAt(haystackCur) == needle.charAt(needleCur)) {
                // 对比两个字符串, 各位相同时两指针右移
                haystackCur++;
                needleCur++;
            } else {
                // 不相同则根据 next 表查找 needleCur 移向的位置
                // needleCur 移动到了开头, 退无可退, 主串指针继续后移
                if (needleCur == 0) haystackCur++;
                else needleCur = next[needleCur];
            }
        }

        return needleCur == needleLen ? haystackCur - needleCur : -1;
    }
}

Python

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
class KMP:
    def get_next_table(self, needle):
        length = len(needle)
        lp, rp = -1, 0
        next_table = [0] * length
        next_table[0] = -1

        while rp < length - 1:
            if needle[lp] == needle[rp] or lp == -1:
                rp += 1
                lp += 1
                next_table[rp] = lp
            else:
                lp = next_table[lp]

        return next_table

    def get_index(self, haystack, needle):
        haystack_len = len(haystack)
        needle_len = len(needle)

        if needle_len == 0: return 0
        haystack_cur, needle_cur = 0, 0
        next_table = self.get_next_table(needle)

        while haystack_cur < haystack_len and needle_cur < needle_len:
            if haystack[haystack_cur] == needle[needle_cur]:
                haystack_cur += 1
                needle_cur += 1
            else:
                if needle_cur == 0: haystack_cur += 1
                else: needle_cur = next_table[needle_cur]

        return haystack_cur - needle_cur if needle_cur == needle_len else -1

Go

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
func getNextTable(needle string) []int {
	length := len(needle)
	lp, rp := -1, 0
	next := make([]int, length)
	next[0] = -1

	for rp < length-1 {
		if lp == -1 || needle[lp] == needle[rp] {
			rp++
			lp++
			next[rp] = lp
		} else {
			lp = next[lp]
		}
	}

	return next
}

func getIndex(haystack, needle string) int {
	haystackLen := len(haystack)
	needleLen := len(needle)

	if needleLen == 0 {
		return 0
	}

	haystackCur, needleCur := 0, 0
	next := getNextTable(needle)

	for haystackCur < haystackLen && needleCur < needleLen {
		if haystack[haystackCur] == needle[needleCur] {
			haystackCur++
			needleCur++
		} else {
			if needleCur == 0 {
				haystackCur++
			} else {
				needleCur = next[needleCur]
			}
		}
	}

	if needleCur == needleLen {
		return haystackCur - needleCur
	} else {
		return -1
	}
}