最长回文子串——java马拉车动态规划中心拓展
程序员文章站
2022-04-17 08:30:18
最长回文子串大概有四种解法左右,这里用java语言解释了其中三种:动态规划、中心拓展、马拉车算法//动态规划算法,转自 (http://www.mamicode.com/info-detail-2567153.html)public class FindLongestPalindrome {public static void main(String[] args) {......
最长回文子串大概有四种解法左右,这里用java语言解释了其中三种:
- 动态规划、
- 中心拓展、
- 马拉车算法
//动态规划算法,转自 (http://www.mamicode.com/info-detail-2567153.html)
public class FindLongestPalindrome {
public static void main(String[] args) {
String s ="abaeffhsdjlahfjskdagkgfdsagafgfdasdfdagsgdfgddffdgdfsfgdfsgfdsgdhgfdgdfdghfggdgdsfghgffdsgdsfdgdhsfgd";
//中心拓展运行效果以及运行时间
long startTime2=System.nanoTime(); //获取开始时间
String s2 = new SolutionFindLongestPalindrome().longestPalindrome(s); //测试的代码段
long endTime2=System.nanoTime(); //获取结束时间
System.out.println("程序运行时间: "+(endTime2-startTime2)+"ns");
System.out.println(s2);
//动态规划运行效果以及运行时间
long startTime3=System.nanoTime(); //获取开始时间
String s3 = new SolutionFindLongestPalindrome().DPlongestPalindrome(s); //测试的代码段
long endTime3=System.nanoTime(); //获取结束时间
System.out.println("程序运行时间: "+(endTime3-startTime3)+"ns");
System.out.println(s3);
//马拉车算法运行效果以及运行时间
long startTime1=System.nanoTime(); //获取开始时间
String s1 = new SolutionFindLongestPalindrome().Manacher(s); //测试的代码段
long endTime1=System.nanoTime(); //获取结束时间
System.out.println("程序运行时间: "+(endTime1-startTime1)+"ns");
System.out.println(s1);
}
}
//中心拓展算法
class SolutionFindLongestPalindrome{
int max = 0;
int low = 0;
public String longestPalindrome(String s) {
if (s.length() == 0) return s;
char[] array = s.toCharArray();
int n = array.length;
for(int mid = 0; mid < n; mid++) {
mid = longestPalindrome(mid, array, n);
}
return s.substring(low, low+max);
}
// Finds longest palindrome where mid index is at mid.
private int longestPalindrome(int mid, char[] array, int n) {
int left = mid-1;
while (mid < n-1 && array[mid] == array[mid+1]) mid++; // All same chars are part of mid
int right = mid+1;
while (left >= 0 && right < n && array[left] == array[right]) {
left--;
right++;
}
int len = right-left-1;
if (len > max) {
max = len;
low = left+1;
}
return mid;
}
//动态规划算法
/**
* DP最重要的就是要能利用到前面的结果来推断当前状态,比暴力优化的地方就在此,暴力需要对每一个字符串做一次O(n)的操作才能判断出结果,也就是整个过程要O(n^3),但DP对每一个字符串的判断时间是O(1),总共是O(n^2)
假设s=adcdf,我们可以的推导过程就像下图(i代表行,表示结尾,表示字符串结尾,j代表列,表示字符串开头)
1 2 3 4 5
1 a
2 ad d
3 adc dc c
4 adcd dcd cd d
5 adcdf dcdf cdf df f
我们用dp[][]来表示所有可能子串是否回文,比如dp[1][2]表示第ad,不回文,所以dp[1][2]=false,根据上面表格可以总结一下
1.当i=j时,dp[j][i]=true
2.i-j=1时,比如dp[1][2]为ad,表示两个相邻的字符,此时我们只要判断str[1]==str[2]就能得出dp[1][2]的结果
3.i-j>1时,我们来看dp[j]ij],首先还是要判断开头和结尾是否相等,也就是判断
str[i]==str[j],假如此时str[i]=str[j],我们还要再看剩下的子串是否回文,
我们可以直接从dp[j+1][i-1]来判断剩下的子串,把结果直接拿来用
dp[j][i]=(str[i]==str[j]) ;i-j<=1
dp[j][i]=(str[i]==str[j])&&dp[j+1][i-1];i-j>1
* */
public String DPlongestPalindrome(String s) {
//如果为空的话直接返回空串
if(s.isEmpty()==true) return "";
int Len=s.length();
if(Len==1) return s;
Boolean[][] dp=new Boolean[Len][Len];
int len=0,max=0,start=0,end=0;
for(int i=0;i<Len;i++) {
for(int j=0;j<=i;j++) {
if(i-j>1) {
dp[j][i]=((s.charAt(i)==s.charAt(j))&&dp[j+1][i-1]);
}else {
dp[j][i]=(s.charAt(i)==s.charAt(j));
}
len=i-j;
if(dp[j][i]==true&&len>=max) {
max=len;
start=j;
end=i;
}
}
}
if(start==end) {
String str="";
return str+s.charAt(0);
}
return s.substring(start, end+1);
}
//马拉车算法
private String preProcess(String s){
int n = s.length();
if (n == 0) return "^$";
String result = "^";
for (int i = 0; i < n; i++) {
result += "#" + s.charAt(i);
}
result += "#$";
return result;
}
public String Manacher(String s) {
char[] T = preProcess(s).toCharArray();
int n = T.length;
int[] P = new int[n];
int C = 0, R = 0;
for (int i = 1; i < n-1; i++) {
int i_mirror = 2*C - i; // equals to i' = C - (i-C)
P[i] = R > i ? Math.min(P[i_mirror], R - i) : 0;
// Attempt to expand palindrome centered at i
while( T[i+1+P[i]] == T[i-1-P[i]] )
P[i]++;
// if palindrome centered at i expand past R
// adjust center based on expanded palindrome
if ( i + P[i] > R) {
C = i;
R = i + P[i];
}
}
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n-1 ; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
int beginIndex = (centerIndex-1-maxLen)/2;
return s.substring(beginIndex, beginIndex+maxLen);
}
}
我博客里有大量的从别的博客复制过来的代码,分析,以及理解,但我一律会在文章后面标记原博客大佬博客名,其中部分会加以连接。 绝无抄袭的意思,只是为了我在复习的时候找博客方便。 如有原作者对此有不满,请在博客留言,我一定会删除该博文。
本文地址:https://blog.csdn.net/weixin_42542536/article/details/85989391
上一篇: 【操作系统学习笔记】一、操作系统概述
下一篇: 智慧农业温室大棚,新一轮农业革命开始了