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

背景

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

原题来自LeetCode的第五题。

➜  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]

于是有了以下的解法

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的马拉车算法解法。这里贴一下我根据思路的整理。

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

➜  ruby leetcode submit 5.longest-palindromic-substring.rb
  ✔ Accepted
	  ✔ 103/103 cases passed (88 ms)
		[WARN] Failed to get submission beat ratio.

OK, 提交成功。

后话

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