最长回文串
最长回文串问题
要求子串连续 与 不连续
import java.util.*;
public class ks_huiwenchuan {
public static int max(int a, int b, int c) {
int m = a;
if(m<b)
m=b;
if(m<c)
m=c;
return m;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String s = scan.nextLine();
int size=s.length();
int [] [] dp = new int[size][size];
for(int i=0; i<size; i++) {dp[i][i]=1;}
for(int len=1; len<size; len++) {
for(int i=0; i+len<size; i++) {
if(s.charAt(i)==s.charAt(i+len))
dp[i][i+len] = dp[i+1][i+len-1]+2;
// 如果子串不要求连续 这里没有检测子串是否是回文数
dp[i][i+len] = max(dp[i][i+len], dp[i+1][i+len], dp[i][i+len-1]);
}
}
System.out.println(dp[0][size-1]);
int max = 1;
int [][] dp2 = new int[size][size];
for(int i=0; i<size; i++) {dp2[i][i]=1;}
for(int len=1; len<size; len++) {
for(int i=0; i+len<size; i++) {
if(s.charAt(i)==s.charAt(i+len))
// 检查去掉两端后 是否为回文字符串
if(dp2[i+1][i+len-1]!=0)
dp2[i][i+len] = dp2[i+1][i+len-1]+2;
if(max<dp[i][i+len])
max=dp[i][i+len];
}
}
System.out.println(max);
}
}