输入一个字符串,请找出该字符串的包含的最长回文子字符串
比如,输入babcd,输出bab
输入abbc,输出bb
#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; } } }动态规划