# 引言

题目链接: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]
}
更新于 阅读次数