# 引言
题目链接：https://leetcode.com/problems/longest-palindromic-substring/description/
# 题目大意
给出一个字符串, 找出其中最长的回文字符串(字符串最大长度为1000)
- Example
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
# 题解
# 一句话题解
Manache Algorithm(马拉车算法), 关于算法详情 Click Here!
复杂度O(n)
# AC代码
c++版本
class Solution
{
public:
bool judgeEqual(int lIndex, int rIndex, string s)
{
if (lIndex < 1 || rIndex > 2 * s.length() + 1)
{
return false;
}
return (lIndex & 1) ? true : s[(lIndex >> 1) - 1] == s[(rIndex >> 1) - 1];
}
// Manache Algorithm
string longestPalindrome(string s)
{
int extendSize = 2 * s.length() + 2;
int curCenter = 0;
int curBoundary = 0;
int rCenter = 0;
int rRadius = 0;
vector<int> pDist(extendSize, 0);
for (int i = 1; i < extendSize; ++i)
{
pDist[i] = curBoundary > i ? min(pDist[2 * curCenter - i], curBoundary - i) : 1;
while (judgeEqual(i - pDist[i], i + pDist[i], s))
{
++pDist[i];
}
if (curBoundary < i + pDist[i])
{
curBoundary = i + pDist[i];
curCenter = i;
}
if (rRadius < pDist[i])
{
rRadius = pDist[i];
rCenter = i;
}
}
return s.substr((rCenter - rRadius) >> 1, rRadius - 1);
}
};go版本
func judgeEqual(lIndex, rIndex int, s string) bool {
if lIndex < 1 || rIndex > len(s)*2+1 {
return false
}
if 0 == lIndex&1 {
return s[(lIndex>>1)-1] == s[(rIndex>>1)-1]
}
return true
}
func longestPalindrome(s string) string {
extendSize := len(s)*2 + 2
var curCenter, curBoundary, rCenter, rRadius int
pDist := make([]int, extendSize)
for i := 1; i < extendSize; i = i + 1 {
if curBoundary > i {
if pDist[2*curCenter-i] < curBoundary-i {
pDist[i] = pDist[2*curCenter-i]
} else {
pDist[i] = curBoundary - i
}
} else {
pDist[i] = 1
}
for judgeEqual(i-pDist[i], i+pDist[i], s) {
pDist[i] = pDist[i] + 1
}
if curBoundary < i+pDist[i] {
curBoundary = i + pDist[i]
curCenter = i
}
if rRadius < pDist[i] {
rRadius = pDist[i]
rCenter = i
}
}
return s[(rCenter-rRadius)/2 : (rCenter-rRadius)/2+rRadius-1]
}
有什么想法，欢迎留下评论。