最长回文字符串——马拉车(Manacher)算法

标签: c++  算法  字符串

最长回文字符串——马拉车(Manacher)算法

说来惭愧,都快要毕业了才写第一篇博客。。。

回文串

回文串呢,就是在一个字符串中,左半部分和右半部分是镜像对称的字符串,比如abcba,就是一个已c为中心点的回文串。当然,abccba也是一个回文串,所以回文串可以是奇数亦可以是偶数。

问题

怎么在一个字符串中求出最长的回文串

正常思路

我们的都会想到从左往右以每个字符为中心往这个字符的两边去拓展搜索字符串的长度,就像是abcbad=>abcbad=>abcbad。但是前面也说到了回文串也可以是偶数长度,那么就也存在从两个字符开始搜索的情况,就像是abccba=>abccba=>abccba。若字符串的长度为n,这样的解法从一个字符开始搜索需要n次,从两个字符开始搜索需要n-1次,每次搜索的长度最长为n(或者说是n/2也一样)。那么时间复杂度应该为O(n²)。我也试过用动态规划的解法但依然逃脱不了n²的时间复杂度。

怎么改进

我们这边先放一个例子

c b a b a b c e

假如我们接下来要从这个a开始搜索,我们就需要往两边一个一个字符低拓展,但能发现,这时候拓展的过程中遍历的字符,在这个’a’的前一个字符’b’的拓展过程中已经都被遍历了,这样我们就做了很多重复的操作。如果我们把前面这个’b’对应的回文串记录下来,那么我们就可以利用回文串的性质来减少重复的操作。

于是就变成了下面这样

C R
c b a b a b c e

C标记已知的,右端最靠右的回文串的中心(不是已知的最长回文串的中心),R标记这个回文串的右端。

由于是逐个搜索,我们肯定已经求得以前面所有字符为中心的最长回文串的半径

i_mirror C i R
char c b a b a b c e
radius 0 0 1 2
index 0 1 2 3 4 5 6 7

设当前字符a的下标为i
char[i]和char[i_mirror]关于中间字符‘b’对称,并且char[i_mirror]对应的回文串半径为1,我们以C标记的字符(b)为轴,将这个回文串翻转过去,会发现翻转过去后没有触及b这个回文串的右边界R,因此,根据回文串的对称性,我们便可以得知,以a为中心的最长回文串的半径 等于 以箭号a为中心的最长回文串的半径=1,填入结果

i_mirror C i R
char c b a b a b c e
radius 0 0 1 2 1
index 0 1 2 3 4 5 6 7

这个结果是符合拓展搜索的结果的

那么偶数长度的回文串怎么办?

我们知道奇数+偶数=偶数+奇数=奇数
如果我们在一个字符串的每个间隔以及整个字符串的两边都加上一个不可能出现在这个字符串中的符号,那么这个字符串的长度一定会变成奇数。假设这个字符为’#’,
例如:

abc=>#a#b#c# 长度为3+4=7
abcd=>#a#b#c#d# 长度为4+5=9

这样处理后我们就可以知道’#‘对应的回文串就是偶数长度的回文串(因为插在两个字符串中间)。
并且为了方便在代码中放防止越界(主要是方便省去越界的判断),在做如上处理后我们往往会在字符串的前和后继续插入两个不可能出现在原字符串中的字符,假定是’$‘和’&’,那么上面的例子就会变成

abc=>$#a#b#c#&
abcd=>$#a#b#c#d#&
上表实际上应为

i_mirror C i R
char $ # c # b # a # b # a # b # c # e # &
radius 0 0 1 0 1 0 3 0 7 0 3
index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

能够直接根据镜像字符确定回文长度的条件

  1. 翻转后不能触及或超出R

由于上面的例子进行镜像翻转后没有触及到边界R,因此我们才可以直接确定char[i]对应最长回文串的radius为char[i_mirror],但如果字符串换成

i_mirror C i R
char $ # a(from) # b # a # b # a # b # a(to) # e # &
radius 0 0 1 0 3 0 5 0 7 0
index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

翻转后左边的a(from)移动到a(to)的位置,但a(to)正好是边界R,我们能够直接判断radius[10]=radius[6]=5吗?不可以。因为我们不知道R右边的字符能不能继续满足我们的游戏规则。假如R右边的字符是’b’而不是’e’,我们却判定radius[10]=5(实际应该是7),那么我们就丢失了长度。当然,对称翻转后超出边界R也同理。

但我们肯定知道,以a为中心的最长回文串的边界至少也会到R,这时候我们就把a标记为C,然后用往两边拓展搜索的方法来更新R
由于char[4]==‘b’!=char[16]==‘e’,所以这一步的结果为

C R
char $ # a(from) # b # a # b # a # b # a(to) # e # &
radius 0 0 1 0 3 0 5 0 7 0 5
index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

翻转操作后是否触及或者超出R可以根据radius[i_mirror]和R-i的大小判断(radius[i_mirror]>=R-i则需要继续拓展搜索)。
2. i<R

我们要尽量使当前字符在R的左边,这样才能利用已知的右端最靠右的回文串的回文特性来减少拓展搜索步骤。因此,当i>=R的时候,我们就应该把C移动到i上,再使R=C,然后我们再继续拓展搜索,这样即使拓展的第一步就不匹配,我们也能够确保新的R>=旧的R。

参考的帖子

上面的帖子中把条件分为三个

  1. 超出了 R
  2. radius [ i_mirror ] 遇到了原字符串的左边界
  3. i 等于了 R

但是我觉得他第二个条件不是很正确,因为即便遇到的是C对应回文串的左边界,我们也应当继续去拓展,不然就会漏掉长度,因此我把他的条件1跟2归结成翻转后不能触及或超出R

为什么马拉车算法的时间复杂度为O(n)?
在下面的代码中可以看到算法中有两重循环,那为什么复杂度不是平方级的呢?我们可以注意到,算法中R总是在尽量往右边靠的,并且往右靠的步长总是等于每次做的拓展搜索的拓展次数,而当我们不需要改变R的时候我们就可以根据i_mirror直接获取所要求的radius。忽略掉其他比较,算法的耗时操作就是每一次拓展搜索的每次拓展比较,而因为R的偏移次数是处理后的字符串predealt的长度,我们就可以知道所有拓展搜索的所有拓展次数总和应∈O(n),故Manacher算法复杂度为O(n)。

还原回原字符串的下标
假设我们已求得最长回文串的中心的下标为center,radius[center]=r,由于每两个字符中间都插入了特殊字符’#’,会发现(center-r)/2就是最长回文字符串的首下标。而回文串的长度,设所求回文串有x个非’#‘字符,则’#'字符有x+1个,而回文串总长度为2r+1,则有x+x+1=2r+1 => x=r。所以长度正好为radius[center]。

C++代码:

pair<int, int> manacher(string s) {
    //对字符串的预处理
    string predealt = string();
    predealt.append("$");
    for (int i = 0; i < s.length(); i++) {
        predealt.append("#");
        predealt.append(string(1,s.at(i)));
    }
    predealt.append("#");
    predealt.append("&");


    int* radius = new int[predealt.length()];
    memset(radius, 0, predealt.length() * sizeof(int));
    int R = 0, C = 0,center=0;//center用于标记最长回文串


    for (int i = 1; i < predealt.length(); i++) {
        int  i_mirror = C - (i - C);
        //两种需要拓展搜索的情况
        if (i >= R || radius[i_mirror] >= R - i) {
            //C移动到i的位置
            C = i;
            //当前字符下标>=R
            if (i >= R) {
                //if (i > R) cout << i << endl;
                R = i;
                i_mirror =i;//关于自己对称还是自己
            }
         	//翻转后触及或超出R
            else {
                radius[i] = R - i;//边界至少到R
             }
            //往两边拓展搜索
            while (predealt[i + radius[i] + 1]  == predealt[i - radius[i] - 1] ) {
                radius[i]++;
                R++;
                //cout << R << endl;
            }
            if (radius[center] < radius[i]) center = i;
        }

        //否则直接根据镜像字符对应的回文串长度确定
        else {
            radius[i] = radius[i_mirror];
        }
        
    }
   
    //所求最长回文串在原字符串中的起始下标以及长度
    int start = (center - radius[center]) / 2, len = radius[center];
    delete[] radius;
    return pair<int, int>(start,len);

}



int main()
{
    string s("qcbcbccde");
    pair<int ,int> p=manacher(s);
    cout <<"字符串\""<<s<<"\"最长回文串的起始下标为:"<< p.first << endl<<"最长回文串的长度为:" << p.second<<endl;

}

运行结果
运行结果
如果我们把代码中//cout << R << endl;和//if (i > R) cout << i << endl;取消注释,跟踪一下R的变化
可以看到结果为
在这里插入图片描述
可以看到R的变化是符合我们预期的由1->2*s.length+3-1的(-1是因为i从1开始)。

版权声明:本文为qq_34025034原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_34025034/article/details/106265374

智能推荐

C语言小函数—二进制与十六进制

测试如下 “` int main() { long int num = 15; } “`...

仿微博或微信的文章多图显示(自定义MultiImageView)

按照一般的规矩,先上张图来供大伙看看 如果大致是大伙们需要实现的功能,不烦一观 自定义MultiImageView 工具类 具体使用 app.gradle中添加依赖 implementation 'com.github.bumptech.glide:glide:4.8.0' AndroidManifest.xml中配置联网权限 <uses-permission android:name=&q...

经典进程同步和互斥问题

经典进程同步与互斥问题 前言 一、生产者-消费者问题 1.问题描述 2.问题分析 3.代码 二、读者-写者问题 1.问题描述&&分析 2.代码 三、哲学家进餐问题 1.问题描述&&分析 2.代码 四、理发师问题 1.问题描述&&分析 2.代码 前言 在多道程序设计环境中,进程同步是一个非常重要的问题,下面讨论几个经典的进程同步问题。 一、生产者-消费...

java设计模式——ThreadLocal线程单例

1、定义一个ThreadLocal线程单例,代码如下: 2、定义一个多线程类,代码如下: 3、定义一个测试类,代码如下: 4、输出结果,如下图:...

【tensorflow】线性模型实战

线性模型:y = 1.477 * x + 0.089   1. 采样数据 采样噪声eps在均值0,方差0.01的高斯分布中,而后在均匀分布U(0,1)中,区间[-10,10]进行n=100次随机采样:   2. 计算误差 循环计算每个点的预测值与真是值之间差的平方并累加,从而获得训练集上的均芳误差损失值。   3. 计算梯度   4. 梯度更新 对权重w和偏...

猜你喜欢

常见损失函数和评价指标总结(附公式&代码)

网上看到一篇很实用的帖子关于常见损失函数和评价指标,收藏下来 本文转载于https://zhuanlan.zhihu.com/p/91511706 ------------------------------------------------------------------------------------------------------------------------------...

为什么 4G/5G 的直播延时依然很高

通信技术的发展促进了视频点播和直播业务的兴起,4G 和 5G 网络技术的进步也使得流媒体技术变得越来越重要,但是网络技术并不能解决流媒体直播的高延迟问题。 本文不会介绍网络对直播业务的影响,而是会分析直播中常见的现象 — 主播和观众之间能够感觉到的明显网络延迟。除了业务上要求的延迟直播之外,有哪些因素会导致视频直播的延迟这么高呢? live-streaming  图 1 - ...

springboot 过滤器Filter vs 拦截器Interceptor 详解

1 前言       最近接触到了过滤器和拦截器,网上查了查资料,这里记录一下,这篇文章就来仔细剖析下过滤器和拦截器的区别与联系。 2 拦截器与过滤器之间的区别 从上面对拦截器与过滤器的描述来看,它俩是非常相似的,都能对客户端发来的请求进行处理,它们的区别如下: 作用域不同 过滤器依赖于servlet容器,只能在 servlet容器,web环境下使用 拦截器依赖于sp...

IDEA环境--JavaWeb项目【分页功能实现】

参考链接:https://www.jianshu.com/p/d108d0cd9acf 1、前言 最近在写一些项目,遇到要使用分页功能的地方,就简单的学习了一下,在此总结一下具体实现的过程以及遇到的问题。 分页功能:当我们写一下web项目时会遇到一个页面要显示很多数据,一下子都显示出来效率会很低,也不美观。这就要用到分页,其作用也就是将数据分割成多个页面来进行显示。 2、项目介绍 这只是一个简单的...

517【毕设课设】基于单片机仓库家庭防火防盗报警系统

【资源下载】下载地址如下: https://docs.qq.com/doc/DTlRSd01BZXNpRUxl 功能简要说明: 1.51单片机+1602液晶+按键+烟雾检测传感器MQ+红外检测+蜂鸣器+DHT11温湿度传感器; 2.按键设置烟雾报警浓度值,温度报警值; 3.当达到报警条件,蜂鸣器响; 5.电路板为PCB腐蚀所做,图文件为altiumdesigner工程文件。 6.程序采用C语言编写...