欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

最长回文子串——java马拉车动态规划中心拓展

程序员文章站 2024-01-05 23:31:10
最长回文子串大概有四种解法左右,这里用java语言解释了其中三种:动态规划、中心拓展、马拉车算法//动态规划算法,转自 (http://www.mamicode.com/info-detail-2567153.html)public class FindLongestPalindrome {public static void main(String[] args) {......

最长回文子串大概有四种解法左右,这里用java语言解释了其中三种:

  1. 动态规划、
  2. 中心拓展、
  3. 马拉车算法

//动态规划算法,转自 (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

相关标签: LeetCode

上一篇:

下一篇: