#include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; int n = s.length(); if(n==1){ cout<<s<<endl; return 0; } int dp[n][n] = {0}; for(int i=0;i<n-1;i++){ if(s[i]!=s[i+1]) dp[i][i+1] = 1; } for(int i=n-3;i>=0;i--) for(int j=i+2;j<n;j++){ if(s[i]==s[j]) dp[i][j] = dp[i+1][j-1]; else dp[i][j] = min(dp[i+1][j], dp[i][j-1])+1; } string t(n+dp[0][n-1], '\0'); int i=0, j=n-1, l=0, r=t.length()-1; while(i<=j){ if(s[i]==s[j]){ t[l++] = s[i++]; t[r--] = s[j--]; }else if(dp[i][j-1]<dp[i+1][j]){ t[l++] = t[r--] = s[j--]; }else{ t[l++] = t[r--] = s[i++]; } } cout<<t<<endl; return 0; }
#include <stdio.h> #include <string.h> #define MAXLEN 5001 #define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) int **getDP(char *str, int len); void freeDP(int **dp, int len); char *getPalStr(char *str, int len, int **dp); int main(void) { int len, **dp; char str[MAXLEN], *res; scanf("%s", str); len = strlen(str); dp = getDP(str, len); res = getPalStr(str, len, dp); printf("%s\n", res); free(res); freeDP(dp, len); return 0; } int **getDP(char *str, int len) { int **dp = (int **) malloc(sizeof(int *) * len); for (int i = len - 1; i >= 0; i--) { dp[i] = (int *) malloc(sizeof(int) * len); dp[i][i] = 0; for (int j = i + 1; j < len; j++) { if (str[i] == str[j]) { dp[i][j] = j - i < 2 ? 0 : dp[i + 1][j - 1]; } else { dp[i][j] = j - i < 2 ? 1 : (MIN(dp[i + 1][j], dp[i][j - 1]) + 1); } } } return dp; } void freeDP(int **dp, int len) { for (int i = 0; i < len; i++) { free(dp[i]); } free(dp); } char *getPalStr(char *str, int len, int **dp) { char *res = (char *) malloc(len + dp[0][len - 1] + 1); res[len + dp[0][len - 1]] = '\0'; int l = 0, r = len + dp[0][len - 1] - 1; int i = 0, j = len - 1; while (i <= j) { if (str[i] == str[j]) { res[l++] = str[i++]; res[r--] = str[j--]; continue; } if (dp[i + 1][j] < dp[i][j - 1]) { res[l++] = str[i]; res[r--] = str[i++]; } else { res[l++] = str[j]; res[r--] = str[j--]; } } return res; }
#include <bits/stdc++.h> using namespace std; int main(){ string str; cin >> str; int len = str.length(); if(len == 1){ cout << str; return 0; } if(len == 2){ if(str[0] == str[1]) cout << str; else { string s(1, str[0]); cout << str + s; } return 0; } vector<vector<int>> dp(len, vector<int>(len,0)); for(int i=0; i<len-1; i++){ dp[i][i+1] = str[i] == str[i+1] ? 0 : 1; } int row = len-3, col = len-1; while(row >= 0){ int j = col; while(j < len){ if(str[row] == str[j]){ dp[row][j] = dp[row+1][j-1]; dp[row][j] = min(dp[row][j], min(dp[row+1][j], dp[row][j-1]) + 1); } else{ dp[row][j] = min(dp[row+1][j], dp[row][j-1]) + 1; } j++; } row--; col--; } int newl = len + dp[0][len-1]; string s(newl, 'a'); int l = 0, r = newl-1; int i = 0, j = len - 1; while(l <= r && i <= j){ if(dp[i][j-1] + 1 == dp[i][j]){ s[l++] = str[j]; s[r--] = str[j--]; }else if(dp[i+1][j] + 1 == dp[i][j]){ s[l++] = str[i]; s[r--] = str[i++]; }else if(str[i] == str[j]){ s[l++] = str[i++]; s[r--] = str[j--]; } } cout << s; return 0; }
for(int j = 1; j < n; j++){ dp[j - 1][j] = str[j - 1] == str[j] ? 0 : 1; for(int i = j - 2; i >= 0; i--){ if(str[i] == str[j]) dp[i][j] = dp[i + 1][j - 1]; else dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1; } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); char[] str = br.readLine().toCharArray(); int n = str.length; int[][] dp = new int[n][n]; for(int j = 1; j < n; j++){ dp[j - 1][j] = str[j - 1] == str[j] ? 0 : 1; for(int i = j - 2; i >= 0; i--){ if(str[i] == str[j]) dp[i][j] = dp[i + 1][j - 1]; else dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1; } } // 还原新的回文字符串 char[] pstr = new char[n + dp[0][n - 1]]; // 回文串的长度 int i = 0; int j = str.length - 1; int left = 0; int right = pstr.length - 1; while(i <= j){ if(str[i] == str[j]){ pstr[left] = str[i]; pstr[right] = str[j]; i++; j--; }else if (dp[i][j - 1] < dp[i + 1][j]){ // 从左边转移过来,将str[j]添加在两端 pstr[left] = str[j]; pstr[right] = str[j]; j--; }else{ // 从下边转移过来,将str[i]添加在两端 pstr[left] = str[i]; pstr[right] = str[i]; i++; } left++; right--; } System.out.println(pstr); } }
package main import "fmt" func main() { var str string fmt.Scanf("%s\n", &str) dp := getDp(str) fmt.Println(getString(str, dp)) } func getDp(str string) [][]int { var ret [][]int = make([][]int, len(str)) for i:=0; i<len(ret); i++ { ret[i] = make([]int, len(str)) } for i:=1; i<len(str); i++ { if str[i-1] == str[i] { ret[i-1][i] = 0 } else { ret[i-1][i] = 1 } } for i:=2; i<len(str); i++ { for j := i-2; j>=0; j-- { if str[i] == str[j] { ret[j][i] = ret[j+1][i-1] } else { if ret[j+1][i] < ret[j][i-1] { ret[j][i] = ret[j+1][i] + 1 } else { ret[j][i] = ret[j][i-1] + 1 } } } } return ret } func getString(source string, dp [][]int) string { var res []byte = make([]byte, len(source) + dp[0][len(source)-1]) sl, sr := 0, len(source)-1 rl, rr := 0, len(res) - 1 for sl <= sr { if source[sl] == source[sr] { res[rl] = source[sl] res[rr] = source[sr] rl++ sl++ rr-- sr-- } else { if dp[sl][sr-1] < dp[sl+1][sr] { res[rl] = source[sr] res[rr] = source[sr] rl++ rr-- sr-- } else { res[rl] = source[sl] res[rr] = source[sl] rl++ rr-- sl++ } } } return string(res) }
#include <iostream> (720)#include <vector> #include <string> (765)#include <algorithm> using namespace std;int main() { string s; cin >> s;int n = s.length(); if (n == 1){ cout << s << endl;return 0; }int dp[10000][10000] = { 0 }; for (int i = 0; i < n - 1; i++){ if (s[i] != s[i + 1]) { dp[i][i + 1] = 1; } } for (int i = 0; i <= n - 3; i++){ for (int j = 2; j > n; j++){ if (s[i] == s[j]){ dp[i][j] = dp[i + 1][j - 1]; } else{ dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]) + 1; } } } int len = dp[0][n - 1] + n; string result(n + dp[0][n - 1], '\0'); int i = 0; int j = n - 1; int l = 0; int r = result.length() - 1; while (i <= j){ if (s[i] == s[j]){ result[l++] = s[i++]; result[r--] = s[j--]; } else if (dp[i][j - 1] < dp[i + 1][j]){ result[l++] = result[r--] = s[j--]; } else{ result[l++] = result[r--] = s[i++]; } } cout << result << endl; return 0; }
#include<cstdio> #include<cstring> #include<vector> using namespace std; char str[5010],str1[10010]; int main(){ while(scanf("%s",str)!=EOF){ int len1=strlen(str); if(len1==1) { printf("%s",str); continue; } vector<vector<int> >dp(len1,vector<int>(len1)); for(int i=0;i<len1-1;++i){ dp[i][i+1]=(str[i]==str[i+1]?0:1); } for(int len=3;len<=len1;++len){ for(int i=0;i+len-1<len1;i++){ if(str[i]==str[i+len-1]) dp[i][i+len-1]=dp[i+1][i+len-2]; else dp[i][i+len-1]=min(dp[i+1][i+len-1],dp[i][i+len-2])+1; } } int l=0,r=dp[0][len1-1]+len1-1; int ll=0,rr=len1-1; str1[r+1]='\0'; while(l<=r&&ll<=rr){ if(dp[ll][rr-1]+1==dp[ll][rr]){ str1[l++]=str[rr]; str1[r--]=str[rr--]; } else if(dp[ll+1][rr]+1==dp[ll][rr]){ str1[l++]=str[ll]; str1[r--]=str[ll++]; }else if(str[ll]==str[rr]){ str1[l++]=str[ll++]; str1[r--]=str[rr--]; } } printf("%s\n",str1); } return 0; }
#include <iostream> (720)#include <string> #include <algorithm> using namespace std; string str, ans; int dp[5007][5007]; int main() { cin >> str; int len = str.length(); for (int i = 0; i < len - 1; ++i) dp[i][i + 1] = str[i] == str[i + 1] ? 0 : 1; for (int k = 2; k < len; ++k) { for (int i = 0; i + k < len; ++i) { int j = i + k; if (str[i] == str[j]) { dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1); dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]); } else { dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1); } } } //cout << dp[0][len - 1] << endl; ans = string(len + dp[0][len - 1], '%'); int i = 0, j = len - 1; int p = 0, q = ans.length() - 1; while (i <= j && p <= q) { if (dp[i][j - 1] + 1 == dp[i][j]) { ans[p++] = str[j]; ans[q--] = str[j]; --j; } else if (dp[i + 1][j] + 1 == dp[i][j]) { ans[p++] = str[i]; ans[q--] = str[i]; ++i; } else { ans[p++] = str[i]; ans[q--] = str[j]; ++i, --j; } } cout << ans << endl; return 0; }
// 一直提示时间复杂度或循环有误,但是在本地自测毫无问题。。求教 var arr=readline().split(''); var len=arr.length; var max=5000; var mystr=''; for(var i=len-1;i>=0;i--){ // 注意 字符串为单个字符时 if(len==1){ print(arr[0]); break; }else{ // 中心点时空格/元素 mymax(arr.slice(0,i),arr.slice(i+1),arr[i]) mymax(arr.slice(0,i),arr.slice(i),[]) } } function mymax(left,right,mid){ var j=0; while(true){ if(left[left.length-1-j]!=right[j]){ if(left.length<=right.length){ left.splice(left.length-j,0,right[j]) }else{ right.splice(j,0,left[left.length-1-j]) } } if((left.length==right.length)&&j==right.length-1&&left[0]==right[j]){ break; } j++; } var lmax=left.concat(mid).concat(right); if(lmax.length<max){ max=lmax.length; mystr=lmax.join('') } } if(len!=1){ print(mystr) }