python 解法 时间复杂度为O(n)

理论支持：从头到尾扫描字符串，每当增加一个新的字母，最大回文串的长度只能增加1或者2，不可能增加更多，并且，新的最大回文串必然要包含这个字母！

证明：如果新增了一个字母，最大回文串的长度增加了3，这是不可能的，例如：abcdefgfedcba，当增加到最后的b或者a时，是不可能增加3个长度的，因为每增加一个字母，前面必然已经存在一个回文子串，且长度比新串小1或者小2.

所以，从头到尾扫描字符串，每增加一个新的字符，判断以这个字符结尾，且长度为maxLen+1或者maxLen+2的子串是否为回文，如果是，更新最大回文子串。

import sys


def longestPalindrome(s):
    if s == s[::-1]: return s
    start, maxLen = 0, 1
    for i in range(len(s)):
        if i - maxLen >= 1 and s[i - maxLen -1:i + 1] == s[i - maxLen - 1:i + 1][::-1]:
            start = i - maxLen - 1
            maxLen += 2
            continue
        if i - maxLen >= 0 and s[i - maxLen:i + 1] == s[i - maxLen:i + 1][::-1]:
            start = i - maxLen
            maxLen += 1
    return s[start:start + maxLen]


for i in sys.stdin.readlines():
    print (longestPalindrome(i.strip()))

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>

#define INF 1000000
using namespace std;

int main(int argc, char** argv)
{
	//freopen("in.txt", "r", stdin);
	string s;
	while (cin >> s)
	{
		if (s.size() <= 1) 
		{
			cout << s << endl;
			continue;
		}
		int maxStart = 0, maxLen = 1;
		for (int i = 0; i < s.size();)
		{
			int j = i, k = i;
			while (k < s.size() - 1 && s[k + 1] == s[k]) ++k;
			i = k + 1;
			while (k < s.size() - 1 && j > 0 && s[k + 1] == s[j - 1]) { ++k, --j;}
			int curLen = k - j + 1;
			if (curLen > maxLen) { maxStart = j; maxLen = curLen; }
		}

		cout << s.substr(maxStart, maxLen) << endl;
	}

	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String s = sc.next();
			String str = "#";
			String res = "";
			for (int i = 0; i < s.length(); i ++ )
				str += s.charAt(i) + "#";
			for (int i = 0; i < str.length(); i ++ )
				res = res.length() >= check(str, i, i).length() ? res : check(str, i, i);
			System.out.println(res);
		}
	}

	public static String check(String str, int left, int right) {
		while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
			left -- ;
			right ++ ;
		}
		return str.substring(left + 1, right).replace("#", "");
	}
}

坑点：这题出在栈下， 我不知道怎么解，明明可以有不用栈更简单的方法做出来，
害的我一直在寻思如何用栈解决。我觉得专项练习，对于数据结构算法这样的练习，
出的题应该是在使用数据结构和算法时会比其他方法更简单，更易于理解。
这样练习才知道数据结构和算法的妙处，不然就变成了为了练习而练习了，这样又有什么意思呢。


#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <functional>
#include <algorithm>
#include <numeric>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

int length (char str[]);
bool isReverse (char sub[]);
void substr (char str[], char sub[], int i, int num);

int length (char str[])
{
	int len = 0;
	while (str[len++]);
	return len - 1;
}

bool isReverse (char sub[])
{
	for (int right = 0, left = length (sub) - 1; right < left; right++, left--)
	{
		if (sub[right] != sub[left])
		{
			return false;
		}
	}
	return true;
}

void substr (char str[], char sub[], int i, int num)
{
	int index = 0;
	for (int x = i; x < num + i; x++)
	{
		sub[index++] = str[x];
	}
}

int main ()
{
	char str[100] = { 0 };
	while ((scanf ("%s", str)) != EOF)
	{
		int flag = 1;
		for (int len = length (str); len > 0 && flag; len--)
		{
			for (int i = 0, num = len; i + len - 1 < length (str) && flag; i++)
			{
				char sub[100] = { 0 };
				substr (str, sub, i, num);
				if (isReverse (sub))
				{
					cout << sub << endl;
					flag = 0;
				}
			}
		}
	}
	return 0;
}

Manacher算法，时间复杂度为O(N)

// write your code here cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

pair<int,int> autoappend(int left,int right, string& num){
    while(left >= 0 && right < num.size() && num[left] == num[right]){
        left--;
        right++;
    }
    return {left + 1, right - 1};
}
int main(){
    vector<string> vc;
    string s;
    while(cin>>s){
        vc.push_back(s);
    }
    for(int i = 0; i < vc.size(); i++){
        int end = 0;
        int start = 0;
        for(int j = 0; j < vc[i].size(); j++){
            auto [left1, right1] = autoappend(j, j, vc[i]);
            auto [left2,right2] = autoappend(j, j + 1, vc[i]);
            if(right1 - left1 > end - start){
                end = right1;
                start = left1;
            }
            if(right2 - left2 > end - start){
                end = right2;
                start = left2;
            }
        }
        cout << vc[i].substr(start,end - start + 1) << endl;
    }
    return 0;
}

运用Mannacher算法改编，添加一数组来存储每一元素的回文长度和最大回文有边界 ；最后找出整体的最大回文长度

def Mannacher(line):
    lenth_line = len(line)
    data = ["$","#"]
    for i in range(lenth_line):
        data.append(line[i])
        data.append("#")

    R = 1
    C = 0
    res = []
    n = 2*lenth_line+2
    rule = [1 for i in range(n)]

    # mannacher 算法改变，添加一res数组，存储回文长度和右边界
    for i in range(n):
        if i<R:
            rule[i] = min(R-i,rule[2*C-i])
        else:
            rule[i] = 1
        while(i-rule[i]>=0 and i+rule[i]<n and data[i-rule[i]]==data[i+rule[i]]):
            rule[i] += 1
        if i+rule[i] > R:
            C = i
            R = i+rule[i]
        res.append([rule[i],C,R])
    for i in range(n):
        if data[i] =="#":
            continue

    # 找到最大回文长度 max_r-1
    rule.sort()
    max_r = rule[-1]

    for node in res[1:]:
        if node[0] == max_r:
            R = int(node[2]/2-1)
            break

    print(line[R-max_r+1:R])



if __name__ == '__main__':
    while(True):
        try:
            line = input().strip()
            Mannacher(line)
        except:
            break

#思路：动态规划 #   1、dp[i][j] = 1表示字符串s从i到j是回文串  dp[i][j] = 0表示字符串s从i到j不是回文串 #   2、如果dp[i][j] = 1， 那么dp[i+1][j-1] = 1


import sys

def manacher(s):

    maxlen = 0

    start = 0

    dp = [[0 for i in range(len(s))] for i in range(len(s))]

    for i in range(len(s)):

        dp[i][i] = 1

        if i+1<len(s) and s[i] == s[i+1]:

            dp[i][i+1] = 1

            maxlen = 2

            start = i

    for i in range(3,len(s)+1):

        for j in range(len(s)-i+1):

            k = i+j-1 

            if dp[j+1][k-1]==1 and s[j]==s[k]:

                dp[j][k] = 1

                if i>maxlen:

                    start = j

                    maxlen = i

    if maxlen>=2:

        return s[start:start+maxlen]

    return 1

for i in sys.stdin.readlines():

    print (manacher(i.strip()))


	

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s;
	while (cin >> s)
	{
		if (s.length() == 1)
		{
			cout << s << endl;
			continue;
		}
		else if (s.length() == 2)
		{
			if (s[0] == s[1])
				cout << s << endl;
			else
				cout << s[0] << endl;
			continue;
		}
		
		string res;
		int maxlength = 0, k;
		for (int i = 1; i < s.length() - 1; i++)
		{
			k = 1;
			while (i - k >= 0 && i + k < s.length() && s[i - k] == s[i + k])
				k++;
			if (k != 1)
			{
				if (maxlength < 2 * k - 1)
				{
					maxlength = 2 * k - 1;
					res.clear();
					for (int j = i - k + 1; j < i + k; j++)
						res += s[j];
				}
			}
		}
		for (int i = 1; i < s.length() - 1; i++)
		{
			k = 0;
			while (i - k >= 0 && i + k + 1 < s.length() && s[i - k] == s[i + k + 1])
				k++;
			if (k != 0)
			{
				if (maxlength < 2 * k)
				{
					maxlength = 2 * k;
					res.clear();
					for (int j = i - k + 1; j < i + k + 1; j++)
						res += s[j];
				}
			}
		}
		if (res.length() == 0)
			cout << s[0] << endl;
		else
			cout << res << endl;
	}	
	return 0;
}

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			String str = in.next();
			int length = str.length();
			String a[] = new String[length];
			for(int i = 0; i<length; i++){
				a[i] = "";
			}
			String b[] = new String[length];
			for(int i = 0; i<length; i++){
				b[i] = "";
			}
			for(int i = 0; i<length; i++){
				for(int j = 0; i-j>=0&&i+j<length; j++){
					if(str.charAt(i-j) != str.charAt(i+j)){
		                break;						
					}
					 a[i] += str.charAt(i-j);
				}
				
				for(int j = 0; i-j>=0&&i+j+1<length; j++){
					if(str.charAt(i-j) != str.charAt(i+j+1)){
		                			break;		
					}	
					 b[i] += str.charAt(i-j);	
				}			
			}

//			for(int i = 0; i<length; i++){
//				System.out.print(a[i]+" ");
//			}
			int max1 = 0;
			int count1 = 0;
			for(int i = 0; i<length; i++){
				if(a[i].length()>max1){
					max1 = a[i].length();
					count1 = i;
				}
			}
			StringBuffer sb1 = new StringBuffer();
			sb1.append(a[count1].substring(1));
			sb1.reverse();
			String m = sb1.toString()+a[count1];
		//	System.out.print(m);
			
			

//			for(int i = 0; i<length; i++){
//				System.out.print(b[i]+" ");
//			}
			int max2 = 0;
			int count2 = 0;
			for(int i = 0; i<length; i++){
				if(b[i].length()>max2){
					max2 = b[i].length();
					count2 = i;
				}
			}
			//System.out.print(count);
			StringBuffer sb2 = new StringBuffer();
			sb2.append(b[count2]);
		    sb2.reverse();
		    String n = sb2.toString()+b[count2];
		//	System.out.print(n);
			

			System.out.print(m.length()>n.length()?m:n);
			
			
		}
		in.close();
	}
}

#include<iostream>
#include<string>
using namespace std;
int main()
    {
    int n,len,i,exit,sa;
    string str,lstr,rstr;
    while(cin>>str)
        {
        exit=0;
        len=str.length();
        for(n=len;n>1;n--)
            {
            for(i=0;i<=len-n;i++)
                {
                lstr=str.substr(i,n);
                string rstr(lstr.rbegin(),lstr.rend());
                sa=lstr.compare(rstr);
                if(sa==0)
                    {
                    exit=1;
                    cout<<lstr<<endl;
                    break;
                }
            }
            if(exit==1)break;
        }
        if(exit==1)continue;
        cout<<str[0]<<endl;
        
    }
    return 0;
}