Manacher算法

Manacher算法用作求字符串中的最长回文串长度。

算法过程

manacher

利用manacher求解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
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
74
75
76
77
78
79
80
81
82
83
84
#
# [5] Longest Palindromic Substring
#
# https://leetcode.com/problems/longest-palindromic-substring/description/
#
# algorithms
# Medium (25.62%)
# Total Accepted: 370.8K
# Total Submissions: 1.4M
# 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"
#
#
#
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if s is None:
return ''

length = len(s)
if length < 2:
return s

s = self.str_trans(s)

length = len(s)
res = [1 for i in range(length)]
right = c = -1
for i in range(length):
res[i] = min(res[2*c-i], right-i) if right > i else 1
while i-res[i] > -1 and i+res[i] < length:
if s[i-res[i]] == s[i+res[i]]:
res[i] += 1
else:
break
res[i] -= 1

if i + res[i] > right:
right = i + res[i]
c = i

lp = max(res)
lp_index = res.index(lp)
lp = s[lp_index-lp:lp_index+lp+1]
return lp.replace('#', '')



def str_trans(self, s):
s = list(s)
for i in range(len(s)):
s[i] = '#' + s[i]
s.append('#')
return ''.join(s)


def main():
s = 'babad'
ex = Solution()
print(ex.longestPalindrome(s))


if __name__ == "__main__":
main()
  • 本文作者: 大护法
  • 本文链接: https://todebug.com/manacher/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 4.0 许可协议。转载请注明出处!
0%