字符串的最长回文子串

1、题目描述

    给出一个字符串，找出一个字符串的最长回文子串，比如输入：babad，输出：bab或aba，输入：dbbd，输出：：bb

2、解题思路

（1）暴力求解

    找出该字符串的每个子串，时间复杂度为O（n^2），判断这个字符串是否为回文子串的时间复杂度为O（n），总的时间复杂度为O(n^3)，C++代码如下：

#include<iostream>
#include<string>
using namespace std;

string LongestPalindrome(string s) {
	/*
		找出字符串中最长的回文子串
	*/
	if (s.size() == 0)
		return "";
	int length = 0;                          //回文串长度
	int pos = 0;                             //回文串起始位置
	for (int i = 0; i < s.size(); i++) {
		int count = 1;
		for (int j = i + 1; j < s.size(); j++) {
			int begin = i;
			int end = j;
			bool mark = true;
			for (int k = 0; begin < end; k++) {
				if (s[begin] != s[end]) {
					mark = false;
					break;
				}
				begin++;
				end--;
				if (begin > end)
					break;
			}
			if (mark == true)
				count = j - i + 1;
		}
		if (count > length) {
			length = count;
			pos = i;
		}
	}
	string output="";
	for (int i = pos; i < pos + length; i++) {
		output = output + s[i];
	}
	cout << output << endl;
	return output;	
}

（2）中心扩展法

        利用回文串的中心对称性，遍历每个字符串时向两边同时扩展，可以找出以该字符串为中心的最大回文子串。

                                   

    但是中心扩展法有一个问题，如果恰好回文串的个数为偶数个，则找不到对称中心，比如：

                                          

    这里有一种比较方便的处理方式，就是对1，2，2，1进行填充，比如说用#进行填充如下：

    

    如上图这样填充之后就又成了一个中心对称的回文串，因此对于一个串进行处理时，先进行扩充，这样可以使中心扩展时比较方便，不用对非中心对称的子串进行特殊处理。 中心扩展法时间复杂度为O（n^2）。C++代码如下：

int SubpPalidromeLen(string str, int index) {
	int i = 1;
	int count = 1;
	while (index+i<str.size()&&index-i>=0&&str[index + i] == str[index - i]) {
		i++;
		count += 2;
	}
	return count;
}

int main() {
	string input = "abbd";
	string temp = "";
	for (int i = 0; i < input.size(); i++) {
		temp += "#";
		temp += input[i];
	}
	temp += "#";
	int max_len = 0;
	int index = 0;
	for (int i = 0; i < temp.size(); i++) {
		int len = SubpPalidromeLen(temp, i);
		if (max_len < len) {
			max_len = len;
			index = i;
		}
	}
	int begin = index - max_len / 2;
	string output = "";
	for (int i = begin; i < begin + max_len; i++)
		if (temp[i] != '#')
			output += temp[i];	
	cout <<output << endl;
	return 0;
}

（3）Manacher算法

    目前还没看懂。

参考：https://segmentfault.com/a/1190000003914228