请选择 进入手机版 | 继续访问电脑版

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

[复制链接]
密战 发表于 2021-1-1 10:31:37 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
最长回文子串大概有四种解法左右,这里用java语言表明确其中三种:

  • 动态规划、
  • 中心拓展、
  • 马拉车算法
//动态规划算法,转自 (http://www.mamicode.com/info-detail-2567153.html)
  1. 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-j1     * */    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=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&#39; = 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
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )