LeetCode_5: Longest Palindromic Substring - LeetCode

# 引言

题目链接：https://leetcode.com/problems/longest-palindromic-substring/description/

给出一个字符串，找出其中最长的回文字符串 (字符串最大长度为 1000)

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Manache Algorithm (马拉车算法), 关于算法详情 Click Here!

复杂度 O(n)

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