Day9-[KMP]难不倒我

代码随想录算法训练营Day9

28. Find the Index of the First Occurrence in a String

KMP 算法: 专注解决,在一个字符串中,查找是否出现另一个串.

由这三位学者发明的：Knuth，Morris和Pratt，取三位学者首字母,KMP.

核心思想:当出现字符串不匹配时,可以记录一部分之前已经匹配的文本内容,避免从头再去做匹配.

暴力解法O(N*M); KMP解法O(N+M).

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # KMP
        # prefix-suffix table
        n = len(haystack)
        m = len(needle)
        # 构建 next 数组，数组长度为匹配串的长度
        next = [0]*m
        jj = 0
        for ii in range(1, m):  # ii从1开始
            while needle[ii] != needle[jj] and jj > 0:
                jj = next[jj-1]
            if needle[ii] == needle[jj]:
                jj += 1
            # 注意next[ii]的位置
            next[ii] = jj
        # Matching
        jj = 0
        for ii in range(n):
            while haystack[ii] != needle[jj] and jj > 0:
                jj = next[jj-1]
            if haystack[ii] == needle[jj]:
                jj += 1
            if jj == m: return ii-jj+1
        return -1
        # TC: O(N+M)
        # SC: O(M)
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

459. Repeated Substring Pattern

KMP的应用

Sol1:移除匹配

拼接s+s, 把首元素和尾元素删除,在其中寻找s.

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        # Sol1: 调用库函数
        # String.find(s, start, end)
        # s: substring; start: the start position of string to conduct finding
        # return (s + s).find(s, 1, -1) != len(s)
        # Sol2： KMP
        ss = s[1:]+s[:-1]
        n = len(ss)
        m = len(s)
        # Generate prefix-suffix table
        next = [0] * m
        jj = 0
        for ii in range(1, m):
            while s[ii] != s[jj] and jj > 0:
                jj = next[jj-1]
            if s[ii] == s[jj]:
                jj += 1
            next[ii] = jj
        # Matching
        jj = 0
        for ii in range(n):
            while ss[ii] != s[jj] and jj > 0:
                jj = next[jj-1]
            if ss[ii] == s[jj]:
                jj += 1
            if m == jj: return True
        return False
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

字符串总结

要不要使用库函数: 如果库函数仅仅是 解题过程中的一小部分, 并且你已经很清楚这个库函数的内部实现原理的话, 可以考虑使用库函数.

双指针回顾

数学篇,字符串篇,链表篇,N数之和篇

通过前后两个指针不算向中间逼近，在一个for循环下完成两个for循环的工作。

只用双指针法时间复杂度为O(n^{2)，但比哈希法的O(n}2)效率高得多，哈希法在使用两层for循环的时候，能做的剪枝操作很有限。

在双指针法：一样的道理，能解决四数之和 (opens new window)中，讲到了四数之和，其实思路是一样的，在三数之和的基础上再套一层for循环，依然是使用双指针法。

对于三数之和使用双指针法就是将原本暴力O(n^{3)的解法，降为O(n}2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。

同样的道理，五数之和，n数之和都是在这个基础上累加。