寻找字符串的最长回文

	#include <iostream>



	#include <string>



	#include <vector>



	#include <algorithm>



	usingnamespacestd;



	 



	intmain(){



	    string str="";



	    string hui="";



	    intbefore=0;



	    cin>>str;



	    intlen=str.size();



	    for(intx=0;x<len;x++){



	        intsum1=0,move1=0,f=0;



	        while((x-move1>=0)&&(x+move1<len)&&str[x-move1]==str[x+move1]){



	            sum1+=2;



	            move1++;



	            f=1;



	        }



	        if(f){



	            sum1--;



	        }



	        intsum2=0,move2=0;



	        while((x-move2>=0)&&(x+move2+1<len)&&str[x-move2]==str[x+1+move2]){



	            sum2+=2;



	            move2++;



	        }



	        if(sum1>sum2){



	            if(before<sum1){



	                hui=str.substr(x-move1+1,2*move1-1);



	                before=sum1;



	            }



	        }



	        else{



	            if(before<sum2){



	                hui=str.substr(x-move2+1,2*move2);



	                before=sum2;



	            }



	        }



	    }



	    cout<<hui;



	    return0;



	}

	
	

		//Manacher算法，参考：https://segmentfault.com/a/1190000008484167
	

	

		#include<bits/stdc++.h>
	

	

		usingnamespacestd;
	

	

		intmain()
	

	

		{
	

	

		    string s;
	

	

		    while(cin >> s)
	

	

		    {
	

	

		        string t ="$#";
	

	

		        for(inti = 0; i < s.size(); i++)
	

	

		        {
	

	

		            t += s[i];
	

	

		            t +="#";
	

	

		        }
	

	

		        vector<int> p(t.size());
	

	

		        p[0] = 0;
	

	

		        intid = 0, mx = 0, resid = 0, resmx = 0;
	

	

		        for(inti = 1; i < t.size(); i++)
	

	

		        {
	

	

		            p[i] = i < mx ? p[2 * id - i] : 1;
	

	

		            while(t[i + p[i]] == t[i - p[i]])
	

	

		                p[i]++;
	

	

		            if(p[i] + 1>mx)
	

	

		            {
	

	

		                mx = p[i] + 1;
	

	

		                id = i;
	

	

		            }
	

	

		            if(p[i] > resmx)
	

	

		            {
	

	

		                resmx = p[i];
	

	

		                resid = i;
	

	

		            }
	

	

		        }
	

	

		        cout << s.substr((resid - resmx) / 2, resmx - 1) << endl;
	

	

		    }
	

	

		    system("pause");
	

	

		    return0;
	

	

		}
	

import java.util.*;

public class Main {
    // 最长回文子串
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int n = s.length();
        int start = 1, end = 1;
        boolean[][] dp = new boolean[n+1][n+1];
        for (int i = n; i > 0; i--) {
            for (int j = i+1; j <= n; j++) {
                if (s.charAt(i-1) == s.charAt(j-1) && (dp[i+1][j-1] || j - i < 3)) {
                    dp[i][j] = true;
                }
                if (dp[i][j] && j-i > end-start) {
                    end = j;
                    start = i;
                }
            }
        }
        System.out.println(s.substring(start-1, end));
    }
}

动态规划方法--改进暴力全子串判断
状态方程：

表示字符串s[i:j+1] 出是否为回文子串的判断，T or F

转态转移方程

又考虑到，长度为2时的回文子串 超了范围，所以限定 j-2 > i
最终状态转移方程为：

s = input()
n = len(s)
if n <= 1:
    print(s)
else:
    p = [[False for _ in range(n)] for _ in range(n)]
    maxlen = 1
    maxsstr = s[0]
    for r in range(1,n):
        for l in range(r):
            if s[l] == s[r] and (r-l<=2 or p[l+1][r-1]):
                p[l][r] = True
                length = r - l +1
                if length > maxlen:
                    maxlen = length
                    maxsstr = s[l:r+1]
    print(maxsstr)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    cin >> str;
    int len = str.size();
    int maxLen = 1;
    int start = 0;
    vector<vector<int>> dp(len, vector<int>(len, 0));
    for (int i = 0; i < len; i++) {
        dp[i][i] = 1;
    }
    for (int i = len - 2; i >= 0; i--) {
        for (int j = i + 1; j <len; j++) {
            if (str[i] == str[j]) {
                if (j - i == 1) {
                    dp[i][j] = 2;
                } else {
                    if (dp[i + 1][j - 1] > 0) {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                }
            }
            if (maxLen < dp[i][j]) {
                maxLen = dp[i][j];
                start = i;
            }
        }
    }
    cout << str.substr(start, maxLen) << endl;
    return 0;
}

import java.util.Scanner;
public class Main {
    private static String res = "";

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String tmp = "";
        for (int i = 0; i < str.length(); i++) {
            for (int j = i + 1; j <= str.lengt***mp = str.substring(i, j);
                if (isDuichen(tmp)) {
                    if (res.length() < tmp.length()) {
                        res = tmp;
                    }
                }
            }
        }
        System.out.println(res);
    }

    private static boolean isDuichen(String str) {
        String rev = new StringBuffer(str).reverse().toString();
        return rev.equals(str);
    }
}

import java.util.*;
public class Main {
    public static int max=-100;
    public static String ss = "";
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
            int len = s.length();
            if(len<=1){
                System.out.println(s);
                return;
            }
          for(int i=0;i<len;i++){
              shuangOrDan(s,i,i);//单
              shuangOrDan(s,i,i+1);//双
          }
           System.out.println(ss); 
    }
    public static void shuangOrDan(String str, int start, int end){
        char ch1,ch2;
        while(start>=0&&end<str.length()){
            ch1 = str.charAt(start);
            ch2 = str.charAt(end);
            if(ch1 == ch2){
                if(end+1-start>max){
                    max = end+1-start;
                    ss = str.substring(start,end+1);
                }
                start--;
                end++;
            }
            else
                break;
        }
    }
}