精华内容
下载资源
问答
  • Manacher算法Java

    2020-06-08 15:46:11
    import java.util.Scanner; public class MainManacher { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.nextLine(); System.out.println(maxLcpsLength...
    import java.util.Scanner;
    
    public class MainManacher {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String str = sc.nextLine();
            System.out.println(maxLcpsLength(str));
        }
    
        public static char[] manacherString(String str) {
            char[] charArr = str.toCharArray();
            char[] res = new char[charArr.length * 2 + 1];
            int index = 0;
            for (int i = 0; i < res.length; i++) {
                res[i] = (i & 1) == 0 ? '#' : charArr[index++];
            }
            return res;
        }
    
        public static int maxLcpsLength (String str) {
            if (str == null || str.length() <= 0)
                return 0;
            char[] charArr = manacherString(str);
            int[] pArr = new int[charArr.length];
            int index = -1;
            int pR = -1;
            int max = -1;
            for (int i = 0; i < charArr.length; i++) {
                pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
                while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
                    if (charArr[i - pArr[i]] == charArr[i + pArr[i]]) {
                        pArr[i]++;
                    } else {
                        break;
                    }
                }
                if (i + pArr[i] > pR) {
                    pR = i + pArr[i];
                    index = i;
                }
    
                if (max < pArr[i] - 1)
                    max = pArr[i] - 1;
            }
            return max;
        }
    }
    

     

    展开全文
  • Manacher算法及其Java实现

    千次阅读 2017-03-14 14:57:36
    Manacher算法及其Java实现Manacher算法及其Java实现 说明 实现步骤 基本过程 完整实现 确定最小半径 具体代码 复杂度分析 参考 原载于天意博文说明现给定一个已知的字符串str[],现在想要在O(n)的时间复杂度之内求出...

    Manacher算法及其Java实现

    原载于天意博文

    说明

    现给定一个已知的字符串str[],现在想要在O(n)的时间复杂度之内求出一个最长的回文子字符串(正着和倒着顺序读一致)。

    Manacher最早发现了可以用O(n)的时间复杂度来解决该问题,所以这种方法称之为Manacher算法

    实现步骤

    基本过程

    求最大回文字串的长度一般要看原串的长度是奇数还是偶数,然后再分别求得,但是Manacher算法的第一个神奇之处,就是把两种字符串都转化为奇数的字符串,从而简化计算:

            // 1.构造新的字符串
            // 为了避免奇数回文和偶数回文的不同处理问题,在原字符串中插入'#',将所有回文变成奇数回文
            StringBuilder newStr = new StringBuilder();
            newStr.append('#');
            for (int i = 0; i < str.length(); i ++) {
                newStr.append(str.charAt(i));
                newStr.append('#');
            }

    例如原来是aaaba的字符串变化之后就是,而且无论原来的字符串是奇数还是偶数,变化之后都是奇数(方便运算)
    snipaste_20170314_141428

    当构建完成新的字符串之后,从左边第一个字符开始遍历,并且记录每一个字符的最大回文半径,(包括自身),比如第一个#的回文半径就是1,左边第一个A的回文半径是2,遍历每一个字符之后,得到一个关于半径的数组,数组最大的值减1就是最大回文字串的长度,例如:

    snipaste_20170314_142301

    完整实现

    Manacher算法引入三个重要的概念(符号可能有所不同):

    第一个是表示已知回文字串的中心点位置id,第二个是已知回文字串最右边的位置right,最后一个就是表示已知字串的回文半径数组rad[]

    对应上面来说,id就是不断遍历的位置信息,right就是回文半径+id-1,rad[]也就是把每一个半径存放起来

    确定最小半径

    假设现在求出了rad[1, …, i],现在要求后面的rad值,再假设现在有个指针k(实际中就是1),从1循环到rad[i],试图通过某些手段来求出[i + 1, i + rad[i] - 1]的rad值

    如图所示,黑色的部分是一个回文子串,两段红色的区间对称相等。因为之前已经求出了rad[i - k],所以可以避免一些重复的查找和判断,有3种情况:

    001az5G6gy6Gck3Wwgu5e&690

    • rad[i] - k < rad[i - k]

    如图,rad[i - k]的范围为青色。因为黑色的部分是回文的,且青色的部分超过了黑色的部分,所以rad[i + k]肯定至少为rad[i]-k,即橙色的部分。那橙色以外的部分就不是了吗?这是肯定的,因为如果橙色以外的部分也是回文的,那么根据青色和红色部分的关系,可以证明黑色部分再往外延伸一点也是一个回文子串,这肯定是不可能的,因此rad[i + k] = rad[i] - k

    001az5G6gy6Gck6wd628a&69020171427

    • rad[i] - k > rad[i - k]

    如图,rad[i-k]的范围为青色,因为黑色的部分是回文的,且青色的部分在黑色的部分里面,根据定义,很容易得出:rad[i + k] = rad[i - k]。

    根据上面两种情况,可以得出结论:当rad[i] - k != rad[i - k]的时候,rad[i + k] = min(rad[i] - k, rad[i - k])

    001az5G6gy6Gck8urVI76&69020143141426

    • rad[i] - k = rad[i - k]

    如图,通过和第一种情况对比之后会发现,因为青色的部分没有超出黑色的部分,所以即使橙色的部分全等,也无法像第一种情况一样引出矛盾,因此橙色的部分是有可能全等的。

    根据已知的信息,我们不知道橙色的部分是多长,因此就需要再去尝试和判断了,但是最少rad[i + k] = min(rad[i] - k, rad[i - k]),当然此时两者相等

    具体代码

        public static int getPalindromeLength(String str) {
            // 1.构造新的字符串
            // 为了避免奇数回文和偶数回文的不同处理问题,在原字符串中插入'#',将所有回文变成奇数回文
            StringBuilder newStr = new StringBuilder();
            newStr.append('#');
            for (int i = 0; i < str.length(); i ++) {
                newStr.append(str.charAt(i));
                newStr.append('#');
            }
    
            // rad[i]表示以i为中心的回文的最大半径,i至少为1,即该字符本身
            int [] rad = new int[newStr.length()];
            // right表示已知的回文中,最右的边界的坐标
            int right = -1;
            // id表示已知的回文中,拥有最右边界的回文的中点坐标
            int id = -1;
            // 2.计算所有的rad
            // 这个算法是O(n)的,因为right只会随着里层while的迭代而增长,不会减少。
            for (int i = 0; i < newStr.length(); i ++) {
                // 2.1.确定一个最小的半径
                int r = 1;
                if (i <= right) {
                    r = Math.min(rad[id] - i + id, rad[2 * id - i]);
                }
                // 2.2.尝试更大的半径
                while (i - r >= 0 && i + r < newStr.length() && newStr.charAt(i - r) == newStr.charAt(i + r)) {
                    r++;
                }
                // 2.3.更新边界和回文中心坐标
                if (i + r - 1> right) {
                    right = i + r - 1;
                    id = i;
                }
                rad[i] = r;
            }
    
            // 3.扫描一遍rad数组,找出最大的半径
            int maxLength = 0;
            for (int r : rad) {
                if (r > maxLength) {
                    maxLength = r;
                }
            }
            return maxLength - 1;
        }

    复杂度分析

    空间复杂度:插入分隔符形成新串,占用了线性的空间大小;RL数组也占用线性大小的空间,因此空间复杂度是线性的。
    时间复杂度:尽管代码里面有两层循环,通过amortized analysis我们可以得出,Manacher的时间复杂度是线性的。由于内层的循环只对尚未匹配的部分进行,因此对于每一个字符而言,只会进行一次,因此时间复杂度是O(n)

    参考

    http://blog.sina.com.cn/s/blog_3fe961ae0101iwc2.html

    https://segmentfault.com/a/1190000003914228#articleHeader7

    http://blog.csdn.net/pi9nc/article/details/9251455

    http://blog.csdn.net/xingyeyongheng/article/details/9310555

    展开全文
  • 最长回文串——manacher算法java实现

    千次阅读 2017-08-09 10:23:51
    manacher算法的思想是 把偶数、奇数长的字符序列变成奇数长度 创建一个与字符串等长的数组,用来记录字符序列相应位置上字符的最长回文半径,半径为1时默认为字符本身。 然后以每个字符为中轴遍历字符序列,之后求...

    最长回文串是一个很好玩的话题,给出一个无序的不定长的字符序列,如何知道里面的最长回文串呢?

    manacher算法的思想是

    1 把偶数、奇数长的字符序列变成奇数长度

    2 创建一个与字符串等长的数组,用来记录字符序列相应位置上字符的最长回文半径,半径为1时默认为字符本身。

    3 然后以每个字符为中轴遍历字符序列,之后求数组的最大值即为最大的半径,即为最长的回文半径。

    最长回文串便迎刃而解了。

    package com.lgy;
    
    
    public class Manacher {
        public static void main(String[] args) {
            String s = "acbahkafojlnavnufnavkvnv";
            doManacher(s);
        }
    
        public static void doManacher(String s) {
            //在字符串两头和质检添加特殊字符转成奇数长度,原理:奇数+奇数+1=奇数,偶数+偶数+1=奇数。
            StringBuffer sb = new StringBuffer();
            sb.append("#");
            for (int i = 0; i < s.length(); i++) {
                sb = sb.append(s.substring(i, i + 1)).append("#");
            }
            s = sb.toString();
    
    //		以每个字符为轴求最长回文串半径,其中半径=1表示字符本身。
            int[] p = new int[s.length()];
            int left, right = 0;
            for (int i = 0; i < s.length(); i++) {
                int len = 1;
                for (left = i - 1, right = i + 1; left >= 0 && right <= (2 * i) && right < s.length(); left--, right++) {
                    if (s.charAt(left) == s.charAt(right)) {
                        len = len + 1;
                        continue;//如果匹配成功就继续
                    } else {
                        break;//不成功就跳出循环
                    }
                }
                p[i] = len;
            }//end wai for
    
            //求最大的p[i]值
            int pos, maxValuePos = 0;
            for (int i = 0; i < p.length - 1; i++) {
                pos = i;
                for (int j = i + 1; j < p.length; j++) {
                    if (p[i] < p[j]) {
                        pos = j;
                        int tep = p[i];
                        p[i] = p[pos];
                        p[pos] = tep;
                    }
                    if (i == 0)
                        maxValuePos = pos;
                }
            }
            //求得的回文串一定是奇数长度
            int realLen = ((p[0] * 2 - 1) - 1) / 2;//最长回文串的长度,去掉其他字符
            System.out.println("最长的回文串长度为:" + realLen);
    
    
    //求最长回文串内容
            String huiwen;
            StringBuffer realHuiwen = new StringBuffer();
            if (realLen == 1) {
                System.out.println("最长回文串为:" + s.charAt(maxValuePos));
            } else {
    //              截出来
                huiwen = s.substring((maxValuePos + 1 - p[0]), maxValuePos + p[0]);
    //             去掉辅助字符
                for (int j = 0; j < huiwen.length(); j++) {
                    if (j % 2 != 0)
                        realHuiwen = realHuiwen.append(huiwen.charAt(j));
                }
                System.out.println("最长回文串为:" + realHuiwen.toString());
            }
    
        }
    }
    


    展开全文
  • Manacher算法,又叫“马拉车”算法,可以在时间复杂度为O(n)的情况下求解一个字符串的最长回文子串长度的问题。一、回文子串的一般解法比较简单的思路是将字符串的每一个字符作为回文子串的中心对称点,每次保存前面...

    Manacher算法,又叫“马拉车”算法,可以在时间复杂度为O(n)的情况下求解一个字符串的最长回文子串长度的问题。

    一、回文子串的一般解法

    比较简单的思路是将字符串的每一个字符作为回文子串的中心对称点,每次保存前面求得的回文子串的最大值,最后得到的就是最长的回文子串的长度,这种方式的时间复杂度是O(n^2)。在求解过程中,基数的回文子串与偶数的回文子串是不一样的。比如最长回文子串为aba,对称中心就是b,如果最长回文子串为abba,则对称中心应该为两个b之间,为了解决这个问题,可以在每个字符两边加上一个符号,具体什么符号(是字符串里面的符号也行)对结果没有影响,比如加上“#”,则上述的两个序列变成了#a#b#a#和#a#b#b#a#,求出的长度分别为6和9,再除以2就可以得到最后的结果3和4。这种方式的时间复杂度太高,下面介绍时间复杂度为O(n)的Manacher算法。

    二、Manacher算法中的基础概念

    在进行Manacher算法时,字符串都会进行上面的进入一个字符处理,比如输入的字符为acbbcbds,用“#”字符处理之后的新字符串就是#a#c#b#b#c#b#d#s#。

    1、回文半径数组radius

    回文半径数组radius是用来记录以每个位置的字符为回文中心求出的回文半径长度,如下图所示,对于p1所指的位置radius[6]的回文半径是5,每个位置的回文半径组成的数组就是回文数组,所以#a#c#b#b#c#b#d#s#的回文半径数组为[1, 2, 1, 2, 1, 2, 5, 2, 1, 4, 1, 2, 1, 2, 1, 2, 1]。

    116aa58b7d81

    要处理的字符串

    2、最右回文右边界R

    一个位置最右回文右边界指的是这个位置及之前的位置的回文子串,所到达的最右边的地方。比如对于字符串#a#c#b#b#c#b#d#s#,求它的每个位置的过程如下:

    116aa58b7d81

    最右回文右边界R过程

    最开始的时候R=-1,到p=0的位置,回文就是其本身,最右回文右边界R=0;p=1时,有回文串#a#,R=2;p=2时,R=2;P=3时,R=6;p=4时,最右回文右边界还是p=3时的右边界,R=6,依次类推。

    3、最右回文右边界的对称中心C

    就是上面提到的最右回文右边界的中心点C,如下图,p=4时,R=6,C=3

    116aa58b7d81

    最右回文右边界的对称中心C

    三、Manacher算法的流程

    首先大的方面分为两种情况:

    第一种情况:下一个要移动的位置在最右回文右边界R的右边。

    比如在最开始时,R=-1,p的下一个移动的位置为p=0,p=0在R=-1的右边;p=0时,此时的R=0,p的下一个移动位置为p=1,也在R=0的右边。

    在这种情况下,采用普遍的解法,将移动的位置为对称中心,向两边扩,同时更新回文半径数组,最右回文右边界R和最右回文右边界的对称中心C。

    第二种情况:下一个要移动的位置就是最右回文右边界R或是在R的左边

    在这种情况下又分为三种:

    1、下一个要移动的位置p1不在最右回文右边界R右边,且cL

    p2是p1以C为对称中心的对称点;

    pL是以p2为对称中心的回文子串的左边界;

    cL是以C为对称中心的回文子串的左边界。

    这种情况下p1的回文半径就是p2的回文半径radius[p2]。

    116aa58b7d81

    p1<=R且cL

    2、下一个要移动的位置票p1不在最右回文右边界R的右边,且cL>pL。

    p2是p1以C为对称中心的对称点;

    pL是以p2为对称中心的回文子串的左边界;

    cL是以C为对称中心的回文子串的左边界。

    这种情况下p1的回文半径就是p1到R的距离R-p1+1。

    116aa58b7d81

    p1<=R且cL>pL

    3、下一个要移动的位置票p1不在最右回文右边界R的右边,且cL=pL;

    p2是p1以C为对称中心的对称点;

    pL是以p2为对称中心的回文子串的左边界;

    cL是以C为对称中心的回文子串的左边界。

    这种情况下p1的回文半径就还要继续往外扩,但是只需要从R之后往外扩就可以了,扩了之后更新R和C。

    116aa58b7d81

    p1<=R且cL==pL

    四、Manacher时间复杂度分析

    从上面的分析中,可以看出,第二种情况的1,2的求某个位置的回文半径的时间复杂度是O(1),对于第一种情况和第二种情况的3,R是不断的向外扩的,不会往回退,而且寻找回文半径时,R之内的位置是不是进行判断的,所以对整个字符串而且,R的移动是从字符串的起点移动到终点,时间复杂度是O(n),所以整个manacher的时间复杂度是O(n)。

    五、Manacher的代码实现

    public static void main(String[] args) {

    String str = "abcdcbafabcdck";

    //String str = "acbbcbds";

    System.out.println(manacher(str));

    }

    public static char[] manacherString(String str){

    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < str.length(); i++) {

    sb.append("#");

    sb.append(str.charAt(i));

    }

    sb.append("#");

    return sb.toString().toCharArray();

    }

    public static int manacher(String str){

    if(str == null || str.length() < 1){

    return 0;

    }

    char[] charArr = manacherString(str);

    int[] radius = new int[charArr.length];

    int R = -1;

    int c = -1;

    int max = Integer.MIN_VALUE;

    for (int i = 0; i < radius.length; i++) {

    radius[i] = R > i ? Math.min(radius[2*c-i],R-i+1):1;

    while(i+radius[i] < charArr.length && i - radius[i] > -1){

    if(charArr[i-radius[i]] == charArr[i+radius[i]]){

    radius[i]++;

    }else{

    break;

    }

    }

    if(i + radius[i] > R){

    R = i + radius[i]-1;

    c = i;

    }

    max = Math.max(max,radius[i]);

    }

    return max-1;

    }

    展开全文
  • Manacher算法

    2016-12-10 20:46:03
    Manacher算法使用id、mx做配合,可以在每次循环中,直接对P[i]的快速赋值,从而在计算以i为中心的回文子串的过程中,不必每次都从1开始比较,减少了比较次数,最终使得求解最长回文子串的长度达到线性O(N)的时间...
  • Manacher算法(转载)

    2018-04-25 20:24:00
    Manacher算法(转载) Manacher算法(转载) 一:背景 二:算法过程分析 三:代码 四:算法复杂度分析 转载自大神: 原帖链接 一:背景 给定一个字符串,求出其最长回文子串。例如: s=”abcd”,...
  • manacher算法(Java实现)

    2019-05-03 21:42:48
    public class Manacher { public static char[] manacherString(String str) { char[] charArr = str.toCharArray(); char[] res = new char[str.length() * 2 + 1]; int index = 0; for (int i = 0; i != ...
  • Manacher算法(附Java源代码) Manacher算法用来解决最长回文子串长度问题,时间复杂度为O(N). package hello; public class Manacher { public static char[] process(char[] str) {//将字符串进行处理 char[] ...
  • Manacher算法详解

    2021-02-28 11:26:00
    首先先让我们来看看最原始的暴力扩展,分析其存在的弊端,以此来更好的理解Manacher算法。暴力匹配暴力匹配算法的原理很简单,就是从原字符串的首部开始,依次向尾部进行遍历,每访问一个字符,就以此字符为中心向...
  • 数据结构与算法之Manacher算法 目录 Manacher算法概述 Manacher算法代码实现 扩展题——如果只能向字符串后面添加字符,怎么让整体串变成回文串,要求填的字符最少 1. Manacher算法概述 Manacher算法,又叫...
  • Manacher算法解决最长回文子串问题 最长回文子串问题,就是给定一个字符串,求出字符串中最长回文子串的长度。回文串就是从头到尾遍历和从尾到头遍历是一模一样的。 暴力求解,把字符串所有子串都找出来,再挨个判断...
  • Java 实现 Manacher 算法

    2017-08-24 21:50:02
    Manacher算法的优点就在于他对p[i]的赋值不再是从1开始,根据回文字符串的对称性,在对p[i]赋初始值时我们可以参考前面已有的点,从而找出p[i]的最小值而不再是直接赋值p[i]=1再进行循环。
  • ////////////////////////Manacher算法///////////////////////// //https://www.jianshu.com/p/116aa58b7d81 //字符串转换:包含头尾的所有字符间隔插入‘#’ public static char [ ] ...
  • 求解最长回文字符串朴素算法最朴素的算法是暴力解法就不谈了,时间复杂度是O(n3)。比最朴素解法稍微好一些的解法是O(n2)的一种解法,思路是从对称轴开始考虑,根据回文字符串长度的奇偶分为两种情况,如果最长的回文...
  • Manacher算法-图片详解

    2021-03-05 11:01:12
    简介: 一个字符串中找到最长回文子串。 求解: 暴力解法: ...Manacher: 回文直径、回文半径:从某个位置开始扩,所扩出的回文的直径和半径。 arr回文半径数组:记录每个位置的回文半径。通过前面计算出来
  • 方法一:马拉车算法 时间复杂度O(n) 这个算法最为关键的一行 r[i] = mx &gt; i ? Math.min(r[2 * id - i], mx - i) : 1;...下面是LeetCode上面的AC代码:(Java) class Solution { ...
  • Manacher算法原理 该算法原型就是求解字符串中的最长回文子串,字符串的长度可能是技术或者偶数,所以首先要对字符串进行填充,例如“abc”变为“#a#b#c#”。 算法中的三个要素 1)回文半径数组(以当前字符...
  • 推荐大家一个视频。...讲manacher算法的。看了好几个博文都不太理解,最后搜了一下视频。很有帮助。 package study.lei.string; import java.util.Scanner; public class Manacher { /** * @par
  • Manacher算法:也叫 “马拉车”算法。Manacher算法的应用范围要狭窄得多,但是它的思想和拓展kmp算法有很多共通支出,所以在这里介绍一下。Manacher算法是查找一个字符串的最长回文子串的线性算法。什么是回文串:...
  • } 2.3 Manacher算法 Manacher算法是一种以O(n)时间复杂度得到最长回文串的算法,以该算法的发明者Manacher老先生名字命名。虽然该算法的解释网上较多,但是有点繁琐和难懂,博主尽量以自己小白的理解力详细地进行...
  • 在之前的文章中,我分析了最长回文子序列的问题,是比较通用的方法,即将最长回文子序列问题转化为我们最常见的LCS问题:通过求字符...答案当然是有啊,就是我们今天要讲的主角,马拉车算法(Manacher),这与普通的解法最
  • manacher算法又称马拉车算法,是用来求解字符串中的最长连续回文子串的 方法,可以将时间复杂度降低到O(n)。马拉车算法的核心思想其实是中心扩展思想的变形,首先先来解释一下常见的求最长回文子串的方法,中心...
  • 今天学习了一下manacher算法,比较难理解的是这一步,mx表示的是当前的对称子串的最右端, id表示的这个子串的中间这个点。2*id-i 表示 i 关于 id 的对称点 j p[i]=mx>i?min(p[2*id-i],mx-i):1; AC代码: /* ****...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,203
精华内容 481
关键字:

manacher算法java

java 订阅