配图理解KMP的NEXT数组

KMP真是记一次忘一次。归根到底，还是没有彻底理解。

为了彻底理解，我们这次来画个图。

理解KMP，最关键的是理解next数组。

next数组是基于需要匹配的字符串的一个数组。

如有字符串target，

我们定义next(i) 为，字符串target[0:i+1]的最长的相同前缀与后缀的长度。

什么叫字符串的前缀？

字符串的前缀就是下标从0开始，连续的不包括最后一个下标的子串。
比如abcd的前缀有a,ab,abc。
同理，字符串的后缀就是包括最后一个下标，不包括第一个下标的连续子串。
所以abcd的后缀有b,bc,bcd。

如何判断最长的相同前缀后缀？

举个例子， target='aabaaba',
当i=0的时候，因为一个字符不存在所谓前缀后缀，我们规定next[0] = 0
当i=1的时候，前缀有a，后缀有a有前缀a等于后缀a。所以next[1]=1。
当i=2的时候，前缀有a，aa，后缀有ab，b，但是没有一个是相同的，所以next[2]=0
当i=5的时候，有前缀aab等于后缀aab。所以next[5]=3。
当i=6的时候，有前缀aaba等于后缀aaba。所以next[6]=4。

我们这里写一个算法。

1
2
3
4
5
6
7
8
9
10
# 假设字符串为niddle, 这里用dp表示next数组。

dp = [0] * len(needle)
j = 0
for i in range(1, len(needle)):
    while (j > 0 and needle[j] != needle[i]):
        j = dp[j-1]
    if needle[i]  == needle[j]:
        j+=1
    dp[i] = j

这个怎么理解？

我们把j放在niddle的0下标处，开始遍历niddle。当前下标为i。 这里的j就可以看成当前的最长前缀后缀长度。

当niddle[i] == niddle[j], 最长前后缀长度加1，继续比较下一个i。

若niddle[j] != niddle[i]， 我们得把j回溯到一个位置k，使得niddle[0:k] 和从niddle[i-1-k:i]相同。这样我们可以直接继续比较j和i。

那么这个k等于多少呢？ 这个k是dp[j-1]。

为什么？ 因为我们知道niddle[:j] 和 niddle[i-1-j:i] 相同， 而 niddle[j-1-k:j] 和 niddle[0:k] 相同。那么必然，niddle[0:k] 也和niddle[i-1-k:i]相同。

这里说得太抽象了，画个图解释一下。

蓝色部分的长度就是k，红色部分的长度就是一开始的j了。

当我们把j移动到k处，继续比较新的j和i，如果还是不一样，自然我们得继续缩小k了。

注意有个细节是不匹配的时候我们把j移动到dp[j-1]，这个时候其实相同的前后缀部分是niddle[:dp[j-1]]，因为dp的定义是长度！

至此，kmp的next数组的生成方式应该是理解了。

KMP 算法

一筹莫展的LeetCode10 正则表达式匹配

基本上是一筹莫展的题目，果断时间再遇到估计也还是一筹莫展。

题目

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
[10] Regular Expression Matching  

https://leetcode.com/problems/regular-expression-matching/description/

* algorithms
* Hard (25.59%)
* Total Accepted:    333.7K
* Total Submissions: 1.3M
* Testcase Example:  '"aa"\n"a"'

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.


'.' Matches any single character.
'*' Matches zero or more of the preceding element.


The matching should cover the entire input string (not partial).

Note:


	s could be empty and contains only lowercase letters a-z.
	p could be empty and contains only lowercase letters a-z, and characters like . or *.


Example 1:


Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".


Example 2:


Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".


Example 3:


Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".


Example 4:


Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".


Example 5:


Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

解读

基本就是要考虑遇到.*以及*的时候。

举个例子来说，

1
2
s = "mississippi"
p = "mis*is*p*."

我们大可跳过前面不是特殊情况的完全匹配的部分，直到

1
2
s = "mi|ssissippi"
p = "mi|s*is*p*."

因为*可以匹配0到多个前面的字符s。所以，我们可以去试着递归匹配

1
2
3
4
5
6
7
8
9
s = "ssissippi"
p = "is*p*."


s = "sissippi"
p = "is*p*."

s = "issippi"
p = "is*p*."

所以基本流程是

  1. 当p长度为0，检查s是否长度为0，是的话返回true，否则返回false。
  2. 当p的长度为1， 检查s的长度是否为1，如果s长度为1，并且s和p相同亦或者p为”.”，则返回true，否则返回false。
  3. 当p[1]不为*的时候递归匹配s[1..-1] p[1..-1]。
  4. 当p[1]为*的时候，这个时候就麻烦了。因为*可以匹配0个到多个p[0]，所以我们得做一次循环，在循环中递归匹配。

Ruby 解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def is_match(s, p)
  return s.length == 0  if p.length == 0
  return s.length == 1 && (s[0] == p[0] || p[0] ==".") if p.length == 1
  if p[1] != "*"
    return false if s.length == 0
    return (s[0] == p[0] || p[0] ==".") && is_match(s[1..-1], p[1..-1])
  end
  temp = s
  while s.length != 0 && (s[0] == p[0] || p[0] == ".")
    result = is_match(s[1..-1], p[2..-1])
    return true if result == true
    s = s[1..-1]
  end
  return is_match(temp, p[2..-1])
end

后话

不看答案我是真的不会，看了答案我还是懵的。

算法 leetcode

最长回文字符串算法-Manacher’s Algorithm 的Ruby解法

背景

Manacher’s Algorithm 是将最大回文字符串算法的复杂度降低到O(n)的算法。

原题来自LeetCode的第五题。

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
➜  my_blog git:(master) ✗ leetcode show 5
[5] Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/description/

* algorithms
* Medium (27.79%)
* Total Accepted:    632.5K
* Total Submissions: 2.3M
* Testcase Example:  '"babad"'

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:


Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.


Example 2:


Input: "cbbd"
Output: "bb"

动态规划解法

假设已经有一个判断字符串是否回文的函数, i = 0, j = s.length

  1. 如果这个字符串s已经是回文，则直接返回这个字符串。

  2. 如果这个字符串s不是回文，我们考虑去寻找两个子字符串的最大回文。s[i+1..j], s[i..j-1]

于是有了以下的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def longest_palindrome(s)
  return s if is_palindrome(s)
  i  = 0
  j  = s.length - 1
  s1 = longest_palindrome(s[i+1..j])
  s2 = longest_palindrome(s[i..j-1])
  return (s1.length > s2.length ? s1 : s2)
end


def is_palindrome(s)
  i = 0
  j = s.length - 1
  while i < j
    return false if s[i] != s[j]
    i += 1
    j -= 1
  end
  return true
end

然后提交之后，Leetcode说，不好意思，超时了。。。两年之前通过的解答为啥超时了？

看了一下，testcase从原来的94增加到了103。。。

之前解题时候只图通过，而没仔细想过优化，上网一找，回文问题还是有固定的最优解决方式的。

马拉车算法

马拉车算法太复杂了。不看答案估计一辈子想不出来，光看思路也是十分费解。

我自然是不打算在这里写一遍思路。单纯引用别人已经整理好的东西即可。

比如这位大哥的解说是我最大致能够看懂的。

点击这里

网上大多数文章并没提供Ruby的马拉车算法解法。这里贴一下我根据思路的整理。

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
def longest_palindrome(s)
  return s if s.length < 2
  s = "#" + s.split('').join("#") + "#"
  i = 0
  c = 1
  j = 2
  r = 2
  p = []
  p[0] = 0
  p[1] = 1
  while j < s.length
    i = 2*c - j
    if r - j <=  p[i]
      p[j] = r - j
      while ( s[j + p[j] + 1] == s[j - p[j] - 1])
         p[j]+=1
      end
      if p[j] + j > r
        c = j
        r = j + p[j]
      end
    else
      p[j] = p[i]
    end
    j = j + 1
  end
  max = p.max
  max_index = p.index(max)
  return s[max_index-max..max_index+max].gsub("#", "")
end
1
2
3
4
➜  ruby leetcode submit 5.longest-palindromic-substring.rb
  ✔ Accepted
	  ✔ 103/103 cases passed (88 ms)
		[WARN] Failed to get submission beat ratio.

OK, 提交成功。

后话

最近又开始刷题了，啊哈啊青春。

算法