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

    2018-08-06 11:55:58
    针对回文字符串的处理,在1975年的时候,Manacher提出了专门的Manacher算法,它的思路是,结合之前已经鉴别出来的回文字符串,鉴别出后面的回文字符串。但是这种算法只对奇回文字符串起作用,为了能够鉴别偶回文字符...

    最长回文子字符串问题:给定一个字符串,找出字符串中的最长的回文子字符串

    思路一,暴力破解

    找出所有的回文子字符串,找出其中最长的字符串

    代码:

    public static String longestPalindrome(String s) {
    	for(int i=s.length()-1;i>=0;i--) {
    		for(int j=0;i+j<s.length();j++) {
    			if(isPalindrome(s.substring(j,i+j+1)))
    				return s.substring(j,i+j+1);
    					
    		}
    	}
    	return null;
    }
    	
    private static boolean isPalindrome(String temp) {
    	for(int i=0,j=temp.length()-1;j>=i;i++,j--) {
    		if(temp.charAt(i)!=temp.charAt(j))
    			return false;
    	}
    	return true;
    }

    时间复杂度是O(N^3),太过于复杂。

     

    思路二,动态规划

    对于一个回文字符串,将其最左边与最右边的字符去掉,得到的子串仍然是回文字符串。发现这种规律,可以考虑使用动态规划。重复上述的“除去最左端最右端的字符得到子字符串”这个过程,最后会得到边界条件:如果是奇回文字符串,最后的边界条件是单个的字符;如果是偶回文字符串,最后的边界条件是两个挨着的相同的字符。我们使用一个二维矩阵来记录某段子串是否是回文字符串。

    代码:

    public String longestPalindrome(String s) {
    	int N=s.length();
    	if(N==0) return null;
    	
    	int max=1;
    	int start=0;
    	boolean[][] p=new boolean[N][N];
    		
    	for(int i=0;i<N;i++) {
    		p[i][i]=true;
    	}
    		
    	for(int i=0;i<N-1;i++) {
    		if(s.charAt(i)==s.charAt(i+1)) {
    			p[i][i+1]=true;
    			max=2;
    		}
    	}
    		
    	for(int len=3;len<=N;len++) {
    		for(int j=0;j+len<=N;j++) {
    			if(s.charAt(j)==s.charAt(j+len-1)&&p[j+1][j+len-2]==true) {
    				p[j][j+len-1]=true;
    				if(len>max) {
    					max=len;
    					start=j;
    				}
    			}
    		}
    	}
    		
    	return s.substring(start, start+max);
    }

    时间复杂度是O(N^2),这种复杂度如果处理特别长的字符串也会消耗大量的时间

     

    思路三,Manacher算法

    针对回文字符串的处理,在1975年的时候,Manacher提出了专门的Manacher算法,它的思路是,结合之前已经鉴别出来的回文字符串,鉴别出后面的回文字符串。但是这种算法只对奇回文字符串起作用,为了能够鉴别偶回文字符串,我们可以在字符串的首尾以及字符之间插入特殊字符,经过这样处理之后,偶回文字符串变成了奇回文字符串,而奇回文字符串仍然是奇回文字符串。

    id是已经找到的回文字符串的对称中心点,Right是右边界,left是左边界,在数组p[]中保存id的回文半径,j是i关于id的对称点,若i<Right,则p[i]=Math.min(Right-i, p[j]),否则p[i]=1。对p[i]进行初始化以后,以i为中心,对i的回文半径p[i]进行更新。更新完毕后,如果i+p[i]>Right,则对Right和id进行更新。

    代码:

    public String longestPalindrome(String s) {
    	StringBuffer temp=new StringBuffer();
    	temp.append("&");
    	for(int i=0;i<s.length();i++) {
    		temp.append("#");
    		temp.append(s.charAt(i));
    	}
    	temp.append("#");
    		
    	int[] p=new int[temp.length()];
    	int id=-1,right=-1;
    	for(int i=1;i<temp.length();i++) {
    		if(i<right) {
    			p[i]=Math.min(right-i, p[2*id-i]);
    		}
    		else
    			p[i]=1;
    			
    		while((i+p[i])<temp.length()&&(i-p[i])>=0&&temp.charAt(i+p[i])==temp.charAt(i-p[i])) {
    			p[i]++;
    		}
    
    		if(i+p[i]>right) {
    			right=i+p[i];
    			id=i;
    		}
    	}
    		
    	int max=0,idx=0;
    	for(int i=0;i<temp.length();i++) {
    		if(p[i]>max) {
    			max=p[i];
    			idx=i;
    		}
    	}
    		
    	return s.substring((idx-max)/2, (idx+max)/2-1);
    	
    }

    时间复杂度是O(N)

    展开全文
  • 文章 https://blog.csdn.net/ncepu_Chen/article/details/88866664 中的矢量图 文章 https://blog.csdn.net/ncepu_Chen/article/details/88866664 中的矢量图 文章 ...
  • manacher算法

    2018-06-09 19:38:53
    manacher算法,适合初学者吧,个人感觉讲的不错,有兴趣的可以看看。。
  • Manacher算法及应用

    2019-07-28 15:54:53
    manacher算法其实是暴力算法的升级版,它在扩的过程记录了几个信息,使扩的过程加速了。 记录了三个信息:回文半径数组,回文中心,回文右边界。 本文主要目的是记录与该算法相关的题型,不对算法进行详解,...

    问题:给定一个字符串str,返回str中最长回文子串的长度

    暴力解法:比如给定 "aba",遍历每个字符,首先来到 a,左右扩,左扩出界,记长度为1。然后来到 b,左右扩,左边的字符等于右边,长度加2,再扩出界,记长度为3。再来到 a,右扩出界,记为1。最长就为3。这种暴力扩法的时间复杂度为O(N^2) !

    注意当字符数量为偶数时,比如 "abba",按照上述扩法是不能找出回文串的,故对原字符进行统一处理,假设原长为n,处理后的长度为2*n+1,即不论原先是奇回文还是偶回文,处理后都变成奇回文! 例如:"aba" 变成 "#a#b#a#"    "abba" 变成 "#a#b#b#a#"

    处理后再按暴力解法求出长度后除以2就得到原字符串最长回文子串的长度。

    Manacher算法解决该问题可以做到时间复杂度为O(N)!!! 

    manacher算法其实是暴力算法的升级版,它在扩的过程记录了几个信息,使扩的过程加速了。

    记录了三个信息:回文半径数组,回文中心,回文右边界。

    本文主要目的是记录与该算法相关的题型,不对算法进行详解,具体算法详解参考:《程序员代码面试指南》。

    题目1:给定一个字符串str,返回str中最长回文子串的长度。

    //构造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 ? '#' : 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++) {
                //i'的回文和i~R的距离,谁更近就是i的瓶颈
                //2 * C - i --> i'的位置
                //pArr[2 * C - i]  i'的回文半径
                //R - i --> i到R的距离
                //R > i i在R的边界里面
                pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
                //全部情况都往外扩,虽然情况2、3扩充一次后会直接失败,但统一简化了代码
                //检查是否越界
                while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
                    if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
                        pArr[i]++;
                    else {
                        break;
                    }
                }
                //如果扩充区域超过了R,做相应的更新
                if (i + pArr[i] > R) {
                    R = i + pArr[i];
                    C = i;
                }
                //记录全局最大值
                max = Math.max(max, pArr[i]);
            }
            return max - 1;
        }
     

    题目2:在字符串后面添加最少字符,使整个字符串都成为回文串。比如 "ab121"  , 输出 "ab121ba"

    该问题等价于找到包含最后一个字符的最长回文子串,所以想到用manacher算法!

    生成manacher字符串函数同上,省略了。

    public static String shortestEnd(String str){
            if(str==null || str.length()==0){
                return null;
            }
            char[] charArr = manacherString(str);
            int[] pArr = new int[charArr.length];
            int C = -1;
            int R = -1;
            int maxContainsEnd = -1;
            for(int i=0;i<charArr.length;i++){
                pArr[i] = i<R ? Math.min(pArr[2*C-i], R-i):1;
                while(i-pArr[i]>=0 && i+pArr[i]<=pArr.length-1){
                    if(charArr[i-pArr[i]]==charArr[i+pArr[i]]){
                        pArr[i]++;
                    }else{
                        break;
                    }
                }
                if(i+pArr[i]>R){
                    R = i+pArr[i];
                    C = i;
                }
                if(R == charArr.length){
                    maxContainsEnd = pArr[i];
                    break;
                }
            }
            char[] res = new char[str.length() - maxContainsEnd +1];
            for(int i=0;i<res.length;i++){
                res[res.length-1-i] = charArr[i*2+1];
            }
            return str+String.valueOf(res);
        }

     

    题目3:给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。 输入: "aacecaaa" 输出: "aaacecaaa"  Leetcode 214题

    public String shortestPalindrome(String s) {
            if(s==null || s.trim().equals("")){
                return s;
            }
            char[] c = manacherString(s);
            int[] p = new int[c.length];
            int C = -1;
            int R = -1;
            for(int i=0;i<c.length;i++){
                p[i] = i<R ? Math.min(p[2*C-i],R-i) : 1;
                while(i-p[i]>=0 && i+p[i]<c.length){
                    if(c[i-p[i]] == c[i+p[i]]){
                        p[i]++;
                    }else{
                        break;
                    }
                }
                if(i+p[i]>R){
                    R = p[i] + i;
                    C = i;
                }
            }
            
            int maxLen = 1;
            for(int i=1;i<p.length;i++){
                if(i-p[i]==-1){
                    maxLen = Math.max(maxLen,(i+p[i])/2);
                }
            }
            StringBuffer s1 = new StringBuffer();
            s1.append(s.substring(maxLen,s.length()));
            s1.reverse();
            s1.append(s);        
            return s1.toString();
        }

     

    题目4:给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。输入: "abc" 输出: 3 解释: 三个回文子串: "a", "b", "c".
    输入: "aaa" 输出: 6说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".   Leetcode 647题

    public int countSubstrings(String s) {
            if(s==null || s.length()==0){
                return 0;
            }
            char[] c = manacherString(s);
            int[] p = new int[c.length];
            int C = -1;
            int R = -1;
            int count = 0;
            for(int i=0;i<c.length;i++){
                p[i] = i<R? Math.min(p[2*C-i],R-i):1;
                while(i-p[i]>=0 && i+p[i]<c.length){
                    if(c[i-p[i]]==c[i+p[i]]){
                        p[i]++;
                    }else{
                        break;
                    }
                }
                if(i+p[i]>R){
                    R = i+p[i];
                    C = i;
                }
                count+=p[i]/2;  //回文半径就是以该字符为中心回文子串的个数  因为长度为原来的2倍,所以除以2!
            }
            return count;
        }

     

    展开全文
  • 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算法(转载)

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

    Manacher算法(转载)

    转载自大神: 原帖链接

    一:背景

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

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

    以上问题的传统思路大概是,遍历每一个字符,以该字符为中心向两边查找。其时间复杂度为 O(n2) 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正好是原字符串中最长回文串的长度。

    接下来的重点就是求解 p 数组,如下图:
    img
    设置两个变量,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[j]表示以 j 为中心的最长回文半径,因此我们可以利用p[j]来加快查找。

    三:代码

    #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算法为线性算法,即使最差情况下其时间复杂度亦为 O(n) O ( n ) ,在进行证明之前,我们还需要更加深入地理解上述算法过程。

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

    (1):j 的回文串有一部分在 id 的之外,如下图:
    img
    上图中,黑线为 id 的回文,i 与 j 关于 id 对称,红线为 j 的回文。那么根据代码此时p[i] = mx - i,即紫线。那么p[i]还可以更大么?答案是不可能!见下图:
    img
    假设右侧新增的紫色部分是p[i]可以增加的部分,那么根据回文的性质,a 等于 d ,也就是说 id 的回文不仅仅是黑线,而是黑线+两条紫线,矛盾,所以假设不成立,故p[i] = mx - i,不可以再增加一分。

    (2):j 回文串全部在 id 的内部,如下图:
    img
    根据代码,此时p[i] = p[j],那么p[i]还可以更大么?答案亦是不可能!见下图:
    img
    假设右侧新增的红色部分是p[i]可以增加的部分,那么根据回文的性质,a 等于 b ,也就是说 j 的回文应该再加上 a 和 b ,矛盾,所以假设不成立,故p[i] = p[j],也不可以再增加一分。

    (3):j 回文串左端正好与 id 的回文串左端重合,见下图:
    img
    根据代码,此时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次,即时间复杂度为: Tworst(n)=O(n) T w o r s t ( n ) = O ( n )

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

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

    展开全文
  • Manacher算法:求解最长回文字符串,时间复杂度为O(N) 回文串定义:“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。回文子串,顾名思义,即字符串中满足回文性质的子串。
  • Manacher算法总结

    万次阅读 多人点赞 2014-12-21 16:10:27
    Manacher算法 算法总结第三弹 manacher算法,前面讲了两个字符串相算法——kmp和拓展kmp,这次来还是来总结一个字符串算法,manacher算法,我习惯叫他 “马拉车”算法。 相对于前面介绍的两个算法,Manacher算法的...
  • Manacher算法进阶问题

    2020-12-29 15:23:05
    Manacher算法进阶问题 题目描述 给定一个字符串str,想通过添加字符的方式使得str整体都变成回文字符串,但要求只能在str的末尾添加字符,请返回在str后面添加的最短字符串 [举例] str = “abcd123321”,在必须包含...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,650
精华内容 3,060
关键字:

manacher算法