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

    万次阅读 多人点赞 2018-10-01 18:31:43
    看了好久的Manacher算法,觉得还是要自己画一遍,自己把代码写一遍才能理解 下面分享一下,如果有错,希望指正 简陋版本的,但是他基本只是做到了求取最长回文字符串,严格来说它并不是Manacher’s Algorithm-马拉车...

    看了好久的Manacher算法,觉得还是要自己画一遍,自己把代码写一遍才能理解

    下面分享一下,如果有错,希望指正

    简陋版本的,但是他基本只是做到了求取最长回文字符串,严格来说它并不是Manacher’s Algorithm-马拉车算法

    #include<stdio.h>   、
    
    char qdu[100050];
    int manachar()
    {
    	int i;
    	int res = 0;
    	for (i = 1; qdu[i]; i++)
    	{
    		int l = i;
    		int r = i;
    		while (qdu[i] == qdu[r + 1])
    			r++;
    		i = r;
    		while (qdu[l - 1] == qdu[r + 1]) 
    		{
    			r++;
    			l--;
    		}
    		if (res < r - l + 1)
    			res = r - l + 1;
    	}
    	return res;
    }
    int main()
    {
    	int loop;
    	qdu[0] = '$';
    	gets(qdu + 1);
    	printf("%d\n", manachar());
    
    	return 0;
    }
    

    Manacher’s Algorithm-马拉车算法 时间复杂度O(n)

    互联网侦察微信公众号讲解,虽然文章很长,但是他讲解的十分清楚

    这篇博文简单的介绍了思路

    下面是核心代码,我们先看图

    //Manacher算法计算过程
    int MANACHER(char *st, int len)
    {
    	int mx = 0, ans = 0, po = 0;//mx即为当前计算回文串最右边字符的最大值
    	for (int i = 1; i <= len; i++)
    	{
    		if (mx > i)
    			Len[i] = min(mx - i, Len[2 * po - i]);//在Len[j]和mx-i中取个小
    		else
    			Len[i] = 1;//如果i>=mx,要从头开始匹配
    		while (st[i - Len[i]] == st[i + Len[i]])
    			Len[i]++;
    		if (Len[i] + i > mx)//若新计算的回文串右端点位置大于mx,要更新po和mx的值
    		{
    			mx = Len[i] + i;
    			po = i;
    		}
    		ans = max(ans, Len[i]);
    	}
    	return ans - 1;//返回Len[i]中的最大值-1即为原串的最长回文子串额长度 
    }
    

    首先对字符串进行预处理,处理原因是防止偶数问题(可看前面的博文)
    处理后的结果进行Manacher算法。
    第一个@是0,其余默认从1开始计数
    首先看3 的左右都是#号所以1+1 = 2;
    到了1,它可以数到6,碰到了@就不相等了,而他的回文字符串长度也是6
    等到了1右边的#号,我们就可以根据对称特点,求出他和1左边的#号是同一个值(前提是这个没有超过有边界,黄色横线所示)
    到这里基本就结束了
    在这里插入图片描述

    在这里插入图片描述

    这里给出完整代码,可以自己跑一编,看看效果

    #define maxn 1000010
    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    char str[maxn] = {"3212343219"};//原字符串
    char tmp[maxn << 1];//转换后的字符串
    int Len[maxn << 1];
    
    //转换原始串
    int INIT(char *st)
    {
    	int i, len = strlen(st);
    	tmp[0] = '@';//字符串开头增加一个特殊字符,防止越界
    	for (i = 1; i <= 2 * len; i += 2)
    	{
    		tmp[i] = '#';
    		tmp[i + 1] = st[i / 2];
    	}
    	tmp[2 * len + 1] = '#';
    	tmp[2 * len + 2] = '$';//字符串结尾加一个字符,防止越界
    	tmp[2 * len + 3] = 0;
    	return 2 * len + 1;//返回转换字符串的长度
    }
    //Manacher算法计算过程
    int MANACHER(char *st, int len)
    {
    	int mx = 0, ans = 0, po = 0;//mx即为当前计算回文串最右边字符的最大值
    	for (int i = 1; i <= len; i++)
    	{
    		if (mx > i)
    			Len[i] = min(mx - i, Len[2 * po - i]);//在Len[j]和mx-i中取个小
    		else
    			Len[i] = 1;//如果i>=mx,要从头开始匹配
    		while (st[i - Len[i]] == st[i + Len[i]])
    			Len[i]++;
    		if (Len[i] + i > mx)//若新计算的回文串右端点位置大于mx,要更新po和mx的值
    		{
    			mx = Len[i] + i;
    			po = i;
    		}
    		ans = max(ans, Len[i]);
    	}
    	return ans - 1;//返回Len[i]中的最大值-1即为原串的最长回文子串额长度 
    }
    
    
    int main()
    {
    	int len = INIT(str);
    	MANACHER(tmp, len);
    }
    
    
    
    展开全文
  • 浅谈Manacher算法

    2020-08-20 12:09:56
    给定一个长度为 nnn 的字符串 S,Manacher 算法可以在 O(n)O(n)O(n) 的时间内计算出分别以 S 中的每个字符为中心,最大回文子串的长度. 通常 Manacher 算法可以用来求解一个字符串中的最长回文子串,或者是统计一个...

    1. 前言

    给定一个长度为 n n n 的字符串 S,Manacher 算法可以在 O ( n ) O(n) O(n) 的时间内计算出分别以 S 中的每个字符为中心,最大回文子串的长度. 通常 Manacher 算法可以用来求解一个字符串中的最长回文子串,或者是统计一个字符串中所有回文子串的个数等.

    2. 字符串预处理

    首先需要对带求解的字符串 S 填充分隔符,在每个字符的两边都插入一个特殊的符号,这里我们取 # 作为分隔符,比如 ABCD 填充之后变成了 #A#B#C#D#;再比如 ABC 填充之后变成了 #A#B#C# . 这样做的好处是能够让填充后的字符串长度始终为奇数.

    3. 算法过程

    令数组 P[i] 记录以字符 S[i] 为中心的最长回文子串向左右扩展的长度(包含 S[i]),问题的核心就是求解出所有的 P[i],以下图为例.

    可以看出,P[i]-1正好是原字符串中以 S[i] 为中心的最长回文串长度.

    Manacher 算法采用递推的方式计算 P[i],也就是说在计算 P[i] 时,P[0],P[1],…,P[i-1] 都已经计算完毕了.

    具体计算 P[i] 时,该算法使用两个辅助变量 idmx,其中 id 为 P[0],P[1],…,P[i-1] 中右边界最大的回文子串的中心下标,mx=id+P[id],也就是这个子串的右边界( S[mx] 并不在以 id 为中心的最长回文串中). 令 j=2*id-i ,也就是说 ji 关于中心 id 的对称点,开始分类讨论:

    • i<mx

      • P[j]<mx-i,那么以 S[j] 为中心的回文子串完全被包含在以 S[id] 为中心的回文子串中,由于 i 和 j 对称,以 S[i] 为中心的回文子串也同样会完全被包含在以 S[id] 为中心的回文子串中,以 S[j] 为中心的最长回文子串和以 S[i] 为中心的最长回文子串完全相同,所以必然有 P[i] = P[j],如下图.
      • P[j]>=mx-i,以 S[j] 为中心的回文子串不一定完全被包含于以 S[id] 为中心的回文子串中,但是根据回文串的对称性,下图中两个绿框所包围的部分是相同的,也就是说以 S[i] 为中心的回文子串,其向右至少会扩张到 mx 的位置,也就是说 P[i]>=mx-i,至于 mx 之后的部分是否对称,需要继续暴力匹配.
    • i>=mx:以 i 为中心,暴力向左右匹配.

    const int maxn=1e5+5;
    int p[maxn<<1];//数组开两倍大小
    
    string init(string s){
        string res="#";
        for(char ch:s){
            res+=ch;
            res+='#';
        }
        return res;
    }
    
    void manacher(string s){
        int len=s.length();
        int id=0,mx=0;
        for(int i=0;i<len;++i){
            p[i]=i<mx?min(p[2*id-i],mx-i):1;
            while(i-p[i]>=0 && i+p[i]<len && s[i+p[i]]==s[i-p[i]]) ++p[i];
            if(i+p[i]>mx){
                mx=i+p[i];
                id=i;
            }
        }
    }
    

    4. 总结

    对于字符串中的每一个位置,只进行一次匹配,Manacher 算法的总体时间复杂度为 O ( n ) O(n) O(n),n 为字符串的长度,填充分隔符后长度是原来的两倍,所以时间复杂度依然是线性的.

    展开全文
  • Manacher算法-图片详解

    2021-03-05 11:01:12
    简介: 一个字符串中找到最长回文子串。 求解: 暴力解法: ...Manacher: 回文直径、回文半径:从某个位置开始扩,所扩出的回文的直径和半径。 arr回文半径数组:记录每个位置的回文半径。通过前面计算出来

    简介:

    一个字符串中找到最长回文子串。

    求解:

    暴力解法:

    分奇数回文和偶数回文。奇回文简单,只需从一个位置向两边扩,对于偶回文,需要添加字符来解决偶回文的问题。(中间加的字符可以是任何字符,即使原字符串中含有的也可以。)
    例如:字符串为11311;其中奇偶均有,需添加字符变成#1#1#3#1#1#。
    在这里插入图片描述
    则最大回文长度为11/2等于5.
    时间复杂度:O(n*n)

    Manacher:

    部分概念:

    回文直径、回文半径:从某个位置开始扩,所扩出的回文的直径和半径。
    arr回文半径数组:记录每个位置的回文半径。通过前面计算出来的加速后面的求解。
    最右回文右边界R:所有位置扩出的回文中最右到达的位置。
    回文右边界中心C:如果有多个均可以到达R,C记录最早到达R的中心

    求解i位置的回文半径:分四种情况
    **

    可能性1:

    **i位置不在回文右边界里面,则暴力破
    在这里插入图片描述

    可能性2:
    i位置在回文右边界里面并且,i关于C的对称点i1的回文边界在LR之间
    在这里插入图片描述
    在这里插入图片描述
    例子:
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210305112545750.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ3NDcwODk5,size_16,color_FFFFFF,t_70
    此时i和i1的回文半径一样(由i与i1关于C对称很容易推出);

    可能性3:
    i 位置在回文右边界里面并且,i关于C的对称点i1的回文边界不在LR之间
    在这里插入图片描述
    例:
    在这里插入图片描述
    此时 i 的回文半径为 i 到R。

    可能性4:

    i1回文半径和L压线。
    此时i到R不用判断,需要从R向外扩,看是否相匹配。
    在这里插入图片描述

    时间复杂度: O(n)

    代码实现(java)

    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 != res.length; i++){
                res[i] = (i & 1) == 0 ? '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 C = -1;
            int R = -1;
            int max = Integer.MIN_VALUE;
            for (int i = 0; i != charArr.length; i++){
                pArr[i] = R > i ? Math.min(pArr[2*C-i],R-i ) : 1;    
                while(i + pArr[i] < charArr.length && i - pArr[i] > -1){   //没分情况2、3,均需要执行一下while循环,只不过2、3就一执行次
                    if (charArr[i +pArr[i]] == charArr[i - pArr[i]])
                        pArr[i]++;
                    else
                        break;
                }
                if(i + pArr[i] > R){
                    R = i + pArr[i];
                    C = i;
                }
                max = Math.max(max,pArr[i]);
            }
            return max - 1;
        }
        public static void main (String[] args){
    
        }
    }
    

    例题:

    题目:只向字符串最后添加字符,使得新串为回文串,并且添加字符最少;
    例如:原串为abc12321;答案为新串abc12321cba
    求解:即为求包含最后一个字符的最长回文串,前面不是的,逆序,添加到最后,组成的新串即为答案。manacher算法中,一旦R到达最后一个位置,便停止。

    左神算法进阶班笔记

    展开全文
  • Manacher 算法讲解

    千次阅读 2018-10-28 10:44:51
    一:背景 给定一个字符串,求出其最长回文子串。例如: s="abcd",最长回文长度为 1; s="ababa",最长回文长度为 5;...1975年,一个叫Manacher的人发明了一个算法,Manacher算法(中文名:...

    一:背景

      给定一个字符串,求出其最长回文子串。例如:

    1. s="abcd",最长回文长度为 1;
    2. s="ababa",最长回文长度为 5;
    3. s="abccb",最长回文长度为 4,即bccb。

    以上问题的传统思路大概是,遍历每一个字符,以该字符为中心向两边查找。其时间复杂度为$O(n^2)$,效率很差。

    1975年,一个叫Manacher的人发明了一个算法,Manacher算法(中文名:马拉车算法),该算法可以把时间复杂度提升到$O(n)$。下面来看看马拉车算法是如何工作的。

     作用:时间复杂度O(n)求解最长回文子串。

    二:算法过程分析

    由于回文分为偶回文(比如 bccb)和奇回文(比如 bcacb),而在处理奇偶问题上会比较繁琐,所以这里我们使用一个技巧,具体做法是:在字符串首尾,及各字符间各插入一个字符(前提这个字符未出现在串里)。

    举个例子:s="abbahopxpo",转换为s_new="$#a#b#b#a#h#o#p#x#p#o#"(这里的字符 $ 只是为了防止越界,下面代码会有说明),如此,s 里起初有一个偶回文abba和一个奇回文opxpo,被转换为#a#b#b#a##o#p#x#p#o#,长度都转换成了奇数

    定义一个辅助数组int p[],其中p[i]表示以 i 为中心的最长回文的半径,例如:

    i012345678910111213141516171819
    s_new[i]$#a#b#b#a#h#o#p#x#p#
    p[i] 1212521212121214121

    可以看出,p[i] - 1正好是原字符串中以i为中心的最长回文串长度

    接下来的重点就是求解 p 数组,如下图:

    前提条件 设置两个变量,mx 和 id 。mx 代表以 id 为中心的最长回文的右边界,

                        也就是  mx = id + p[id]

    目的 :               求p[i],也就是以 i 为中心的最长回文半径,

    如果i < mx,如上图,那么:

    if (i < mx)  
        p[i] = min(p[2 * id - i], mx - i);

     解释下代码含义: 首先 : 2 * id - i 为 i 关于 id 的对称点即上图的 j 点,

                                      假设我们都已经求出:p[id] 、p[j] ,其中 p[j]以 j 为中心的最长回文半径

                                        p[id]以id为中心的最长回文半径。

                                      那我们可以就利用 p[j] 和 p[id] 来加快查找,

                                      为什么?看图说话,从上图 ,我们只能看出  p[i]  等于 mx-i 和 p[id] 较小的那个,

                                      也就是  p[i] = min (p[2 * id - i], mx - i )  ;但是  p[i] 有可能:还可以变大,或者不能变大了,

                                      但是 我们不能 从比较过得数据推算出来,

                                       只能从p[i] = min (p[2 * id - i], mx - i ) 开始,继续老老实实的找; 

                                        为什么是O(n)最后再说。

                                       

     

       如果 i >=mx  就老老实实的一个一个找。

     

    三:算法复杂度分析

    文章开头已经提及,Manacher算法为线性算法,即使最差情况下其时间复杂度亦为$O(n)$,在进行证明之前,我们还需要更加深入地理解上述算法过程。

    根据回文的性质,p[i]的值基于以下三种情况得出:

    (1):j 的回文串有一部分在 id 的之外,如下图:

    上图中,黑线为 id 的回文,i 与 j 关于 id 对称,红线为 j 的回文。那么根据代码此时p[i] = mx - i,即紫线。那么p[i]还可以更大么?答案是不可能!见下图:

    假设右侧新增的紫色部分是p[i]可以增加的部分,那么根据回文的性质,a 等于 d ,也就是说 id 的回文不仅仅是黑线,而是黑线+两条紫线,矛盾,所以假设不成立,故p[i] = mx - i,不可以再增加一分。

    (2):j 回文串全部在 id 的内部,如下图:

    根据代码,此时p[i] = p[j],那么p[i]还可以更大么?答案亦是不可能!见下图:

    假设右侧新增的红色部分是p[i]可以增加的部分,那么根据回文的性质,a 等于 b ,也就是说 j 的回文应该再加上 a 和 b ,矛盾,所以假设不成立,故p[i] = p[j],也不可以再增加一分。

    (3):j 回文串左端正好与 id 的回文串左端重合,见下图:

    根据代码,此时p[i] = p[j]p[i] = mx - i,并且p[i]还可以继续增加,所以需要

    while (s_new[i - p[i]] == s_new[i + p[i]]) 
        p[i]++;

    根据(1)(2)(3),很容易推出Manacher算法的最坏情况,即为字符串内全是相同字符的时候。在这里我们重点研究Manacher()中的for语句,推算发现for语句内平均访问每个字符5次,即时间复杂度为:$T_{worst}(n)=O(n)$。

    同理,我们也很容易知道最佳情况下的时间复杂度,即字符串内字符各不相同的时候。推算得平均访问每个字符4次,即时间复杂度为:$T_{best}(n)=O(n)$。

    综上,Manacher算法的时间复杂度为$O(n)$

    四:代码

    #include <iostream>  
    #include <cstring>
    #include <algorithm>  
    
    using namespace std;
    
    char s[1000];
    char s_new[2000];
    int p[2000];
    
    int Init()
    {
        int len = strlen(s);
        s_new[0] = '$';
        s_new[1] = '#';
        int j = 2;
    
        for (int i = 0; i < len; i++)
        {
            s_new[j++] = s[i];
            s_new[j++] = '#';
        }
    
        s_new[j] = '\0';  // 别忘了哦
        
        return j;  // 返回 s_new 的长度
    }
    
    int Manacher()
    {
        int len = Init();  // 取得新字符串长度并完成向 s_new 的转换
        int max_len = -1;  // 最长回文长度
    
        int id;
        int mx = 0;
    
        for (int i = 1; i < len; i++)
        {
            if (i < mx)
                p[i] = min(p[2 * id - i], mx - i);  // 需搞清楚上面那张图含义, mx 和 2*id-i 的含义
            else
                p[i] = 1;
    
            while (s_new[i - p[i]] == s_new[i + p[i]])  // 不需边界判断,因为左有'$',右有'\0'
                p[i]++;
    
            // 我们每走一步 i,都要和 mx 比较,我们希望 mx 尽可能的远,这样才能更有机会执行 if (i < mx)这句代码,从而提高效率
            if (mx < i + p[i])
            {
                id = i;
                mx = i + p[i];
            }
    
            max_len = max(max_len, p[i] - 1);
        }
    
        return max_len;
    }
    
    int main()
    {
        while (printf("请输入字符串:\n"))
        {
            scanf("%s", s);
            printf("最长回文长度为 %d\n\n", Manacher());
        }
        return 0;
    }

     

    展开全文
  • Manacher算法

    2019-03-29 17:12:40
    Manacher算法详解及模板(求解最长回文串) 【面试现场】如何找到字符串中的最长回文子串? Manacher算法详解 以上的几篇博客推荐给大家,嘿嘿 Manacher算法是查找一个字符串的最长回文子串的线性算法。 回文的...
  • 文章目录Manacher算法的图示理解和代码实现需要解决的问题第一种:暴力解法第二种:Manacher算法求解Manacher算法中的三个概念:Manacher算法中分四种情况讨论Manacher算法的代码实现Manacher算法的应用 Manacher...
  • Manacher算法详解

    2017-05-13 20:43:48
    在介绍算法之前,首先介绍一下什么是回文串,所谓回文串,简单来说就是正着读和反着读都是一样的字符串,比如abba,noon等等,一个字符串的最长回文子串即为这个字符串的子串中,是回文串的最长的那个。 计 算...
  • Manacher算法详解及模板(求解最长回文串)

    千次阅读 多人点赞 2018-08-15 20:58:42
    Manacher用于求解最长回文子串。所谓回文串,便是&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;quot;abccba&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;quot;或是斗鸡山上山鸡斗这一类的,你会发现从左...
  •   Manacher算法/马拉车算法是LeetCode647. 回文子串所用的算法。该算法可用于寻找回文子串、回文子串数、最长回文子串长度等问题。   回文字符串,其含义是一个字符串正向还是反向读都是一样的。例如“abba",...
  • } 2.3 Manacher算法 Manacher算法是一种以O(n)时间复杂度得到最长回文串的算法,以该算法的发明者Manacher老先生名字命名。虽然该算法的解释网上较多,但是有点繁琐和难懂,博主尽量以自己小白的理解力详细地进行...
  • manacher算法

    2014-12-03 17:20:20
    /*哈哈,最暴力的办法就是判断每一个字符串是否为回文,然后...now,现在manacher算法复杂度是O(n),主要理解几点, 图解我就不画了哈*/ #include #include #include using namespace std; int p[10001]; char s
  • Manacher(马拉车)算法详解

    万次阅读 多人点赞 2018-03-30 21:13:18
    原文链接传送门 &amp;amp;nbsp; &amp;amp;...马拉车用于解决最长回文子串问题,重点是子串,而不是...所以对于求最长回文子串的问题有一种神奇的算法——马拉车算法,神奇就神奇在时间复杂度为O(n)。&amp;
  • 马拉车(Manacher)算法 解题思路 代码实现 代码优化 性能分析 参考 动态规划算法 解题思路 考虑 “ababa” 这个示例。如果我们已经知道“bab” 是回文,那么很明显,“ababa” 一定是回文,因为它的左首...
  • 而马拉车算法的本质,是对暴力枚举字符串回文中心的优化,充分利用了回文串的对称性。 为了方便说明,现在只考虑奇回文字串,即长度为奇数的回文子串。(偶回文字串同理,在最后面会说明二者如何统一) d[]数组,d[i...
  • Manacher

    2019-01-30 22:35:00
    江湖人称:马拉车算法 解决的问题:求一个字符串中的最长回文。 暴力的方法:遍历字符串,以当前字符为...Manacher算法:是记录并利用以前遍历过的回文,巧妙的达到一个加速的效果。时间复杂度O(n) 首先了解...
  • 马拉车算法 Manacher Algorithm (代码分析) 本节引用自作者:233 Magic,讲解的很清晰,感谢作者分享 链接: https://www.zhihu.com/question/37289584/answer/71483487 我们再规定两个数组与几个变量的...
  • 笔试面试算法经典--最长回文子串

    万次阅读 多人点赞 2017-04-25 20:49:18
    时间复杂度O(n),空间复杂度O(n)观察上面的中心扩展法,发现遍历到每一个元素的时候都要进行一次中心扩展,完全没有利用前面回文子串的信息,Manacher算法的核心思想,就是利用前面遍历的时候产生的回文子串,如...
  • AC自动机 算法详解(图解)及模板

    万次阅读 多人点赞 2018-10-05 22:17:32
    其中,KMP是用于一对一的字符串匹配,而trie虽然能用于多模式匹配,但是每次匹配失败都需要进行回溯,如果模式串很长的话会很浪费时间,所以AC自动机应运而生,如同Manacher一样,AC自动机利用某些操作阻止了模式串匹配阶段...
  • KMP算法详解 - python

    2019-09-27 15:30:27
    References ...Refer to 牛客算法进阶班 (第一章 KMP算法和Manacher算法详解2018.10.14) KMP算法 1. 原始问题 对于一个字符串str(长度为N)和另一个字符串match(长度为M),如果match是str...
  • 求一个字符串的最长子串,Manacher算法是一种O(n)的算法,很给力! s2[0] = '$',是避免在循环中对数组越界的检查。 老大的代码: http://www.cnblogs.com/BigBallon/p/3816890.html 详细的图解: ...

空空如也

空空如也

1 2 3 4 5
收藏数 92
精华内容 36
关键字:

manacher算法图解