文档章节

最长回文子串与Manacher算法

yejq8
 yejq8
发布于 2015/05/16 13:21
字数 1053
阅读 434
收藏 0

题目描述
给定一个字符串,求它的最长回文子串的长度。


最简单粗暴的方法就是,枚举全部的字符串,然后每个都判断一下是不是回文,然后得到长度最长的字符串。显然,这个方法是可行的,可是也是效率极其低下的。

聪明一点的办法是枚举以每个字符作为中心,然后向两边扩展的字符串

例如字符串abcba:

    以a为中心扩展,则最大回文长度为1

    以b为中心扩展,因为a!=c,所以,最大回文长度也是1

    以c为中心,有b==b,a==a,最大回文长度是5

    ......

    得到最大回文长度是5

int LongestPalindrome(const char * s, int n) {
  int i, j, max, c;
  if (s == NULL || n < 1) {
    return 0;
  }
  max = 0;

  for(i = 0; i < n; i++) {
    for(j = 0; (i - j >= 0) && (i+j < n); j++) {
      if (s[i - j] != s[i + j])
    break;
      c = j * 2 + 1;
    }
    if (c > max)
      max = c;
    for(j = 0; (i - j >= 0) && (i + j + 1 < n); j++) {
      if (s[i - j] != s[i + j + 1])
    break;
      c = j * 2 + 2;
    }
    if (c > max)
      max = c;
  }
  return max;
}


    由于奇数和偶数中心的问题如,abba,这是一个偶数的回文字符串,所以b都是中心位置;abcba,这则是一个奇数的回文字符串,中心为c。


    这个算法有两层for循环,那么,有没有更优的方法呢?答案是肯定的。

    Manacher算法提供了一种很巧妙的方法

    

    The-Art-Of-Programming-By-July书上讲的很清楚:


    首先通过在每个字符的两边都插入一个特殊的符号,将所有可能的奇数或偶数长度的回文子串都转换成了奇数长度。比如 abba 变成 #a#b#b#a#, aba变成 #a#b#a#。

    此外,为了进一步减少编码的复杂度,可以在字符串的开始加入另一个特殊字符,这样就不用特殊处理越界问题,比如$#a#b#a#。

    以字符串12212321为例,插入#和$这两个特殊符号,变成了 S[] = "$#1#2#2#1#2#3#2#1#",然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左或向右扩张的长度(包括S[i])。

    比如S和P的对应关系:

     - S  #  1  #  2  #  2  #  1  #  2  #  3  #  2  #  1  #
     - P  1  2  1  2  5  2  1  4  1  2  1  6  1  2  1  2  1

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

    接下来怎么计算P[i]呢?Manacher算法增加两个辅助变量id和mx,其中id表示最大回文子串中心的位置,mx则为id+P[id],也就是最大回文子串的边界。得到一个很重要的结论:
- 如果mx > i,那么P[i] >= Min(P[2 * id - i], mx - i)

——《The-Art-Of-Programming-By-July》


    其实,简单来说就是,j是当前下边i关于id(当前所能到达最右端的中心下标)的对称点,因为是mx是能到达最右端的下标,所以mx-i > 对称点的最大回文长度时候,以当前下标为中心的回文长度应该大于等于对称点的回文长度(因为回文也是对称的);当mx-i<对称点的时候,因为不能确定mx以后的字符的对称性,所以只能判断出mx-i是以当前下标为中心的回文长度的最小值。

    这个算法的优点在于,它不仅解决了奇偶数的讨论问题,还记录了当前字符串的“回文状态”,利用回文来求回文 ,保存了枚举的信息,使得算法能够在线性时间内完成检索任务。

int Manacher(char * str, int n) {
  char s[2004];
  int i, j;
  int t = 0;
  int ret = 1;
  int p[2004], mx = 0, id = 0;
  memset(p, 0, sizeof(p));
  
  s[0] = '$';
  for(i = 1; i < 2 * n + 2; i++) {
    if(i & 1) {
      s[i] = '#';
    } else {
      s[i] = str[t++];
    }
  }
  s[i] = '@';
  s[i+1] = '\0';

  for (i = 1; s[i] != '\0'; i++) {
    p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
    while(s[i+p[i]] == s[i-p[i]]) {
      p[i]++;
    }
    if (i + p[i] > mx) {
      mx = i + p[i];
      id = i;
    }
    ret = max(ret, p[i]);
  }
  
  return ret-1;
}


    引用:The-Art-Of-Programming-By-July

© 著作权归作者所有

下一篇: 判断回文
yejq8
粉丝 0
博文 11
码字总数 8967
作品 0
广州
程序员
私信 提问
Manacher's Algorithm 马拉车算法

这个马拉车算法Manacher‘s Algorithm是用来查找一个字符串的最长回文子串的线性方法,由一个叫Manacher的人在1975年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性,这是非常了...

机器的心脏
2017/12/02
0
0
算法与数据结构(五):Manacher's Algorithm 马拉车算法总结

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 https://blog.csdn.net/Dbyfreedom/article/details/93191052 Manacher’s Algorithm 马拉车...

dby_freedom
06/21
0
0
马拉车算法(Manacher's Algorithm)

这是悦乐书的第343次更新,第367篇原创 Manacher's Algorithm,中文名叫马拉车算法,是一位名叫Manacher的人在1975年提出的一种算法,解决的问题是求最长回文子串,神奇之处在于将算法的时间...

小川94
06/04
0
0
leetcode解题系列-最长回文子串最全解法

前言 本人是一个一名前端菜🐔,正在努力加班加点学习中,看着大佬们写的文章、demo啥的,羡慕不已。盼望着大佬们哪天能给个内推机会啥的那就nice了。 最近刷leetcode刷到这个题目,也在网上...

爱bug的小青年
06/21
0
0
你需要的LeeCode题No.05——“最长回文子串”_一点课堂(多岸学院)

最长回文子串 题目:最长回文子串 描述:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。...

程伟鑫
09/11
14
0

没有更多内容

加载失败,请刷新页面

加载更多

开发中常用的正则表达式

为了能够更好地理解如何在C#环境中使用正则表达式,这里整理了一些常用的正则表达式: 罗马数字: string p1 = "^m*(d?c{0,3}|c[dm])" + "(l?x{0,3}|x[lc])(v?i{0,3}|i[vx])$";string t1 ......

木庄
37分钟前
4
0
【.NET程序打包】VS2019使用Installer Projects打包

C#—使用Installer Projects打包桌面应用程序 前言 打包桌面应用程序实在是一个不常使用的东西,偶尔使用起来经常会忘东忘西的耽误时间,因此,这篇文章多以图片记录过程,也是用于备忘。 下...

_Somuns
41分钟前
4
0
自定义注解,使用动态代理解决网站的字符集编码问题

第1章设置环境 安装操作系统,安装备份(镜像): JDK: 设置环境变量Eclipse:解压即可 Eclipse自身解压目录不包括中文 代码工作空间目录不包括中文Tomcat:解压不要包含中文目录M...

蓝来杯往
46分钟前
6
0
Solr中的字段类型field type

Solr含有多种字段类型,可用的字段类型基本都定义在了包org.apache.solr.schema中,列举如下: 类 说明 BinaryField 二进制数据 BoolField 布尔值,其中’t’/’T’/’1’都是true Collatio...

gantaos
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部