【转载】最长回文字符串(manacher算法)

原文转载自:http://blog.csdn.net/lsjseu/article/details/9990539
偶然看见了人家的博客发现这么一个问题,研究了一下午, 才发现其中的奥妙。Stupid。

题目描述:
回文串就是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。
回文子串,顾名思义,即字符串中满足回文性质的子串。
给出一个只由小写英文字符a,b,c…x,y,z组成的字符串,请输出其中最长的回文子串的长度。

输入:
输入包含多个测试用例,每组测试用例输入一行由小写英文字符a,b,c…x,y,z组成的字符串,字符串的长度不大于200000。

输出:
对于每组测试用例,输出一个整数,表示该组测试用例的字符串中所包含的的最长回文子串的长度。

样例输入:

abab
bbbb
abba

样例输出:

3
4
4

思路:

回文串包括奇数长的和偶数长的,一般求的时候都要分情况讨论,这个算法做了个简单的处理把奇偶情况统一了。原来是奇数长度还是奇数长度,偶数长度还是偶数长度。

算法的基本思路是这样的,把原串每个字符中间用一个串中没出现过的字符分隔#开来(统一奇偶),同时为了防止越界,在字符串的首部也加入一个特殊符$,但是与分隔符不同。同时字符串的末尾也加入’\0’.

算法的核心:用辅助数组p记录以每个字符为核心的最长回文字符串半径。也就是p[i]记录了以str[i]为中心的最长回文字符串半径。p[i]最小为1,此时回文字符串就是字符串本身。

  先看个例子:

  原串:        w aa bwsw f d
  新串:     $ # w# a # a # b# w # s # w # f # d #

辅助数组P: 1 2 1 2 3 2 1 2 1 2 1 4 1 2 1 2 1 2 1

首先看代码(借助http://blog.csdn.net/thyftguhfyguj/article/details/9531149):

 #include <stdio.h>    
    #include <iostream>  
    using namespace std;  

    char s[200002];    
    char str[400010];    
    int p[400010];    

    int min(int a,int b){    
        return a < b ? a : b;    
    }    

    int pre(){    
        int i,j = 0;    
        str[j++] = '$';//加入字符串首部的字符串    
        for(i = 0;s[i];i++){    
            str[j++] = '#';  //分隔符  
            str[j++] = s[i];    
        }    
        str[j++] = '#';    
        str[j] = '\0';  //尾部加'\0'  
        cout<<str<<endl;  
        return j;    
    }    

    void manacher(int n){    
        int mx = 0,id,i;    
        p[0] = 0;    
        for(i = 1;i < n;i++){    
            if(mx > i)  //在这个之类可以借助前面算的一部分  
                p[i] = min(mx - i,p[2 * id - i]); //p[2*id-i]表示j处的回文长度   
            else  //如果i大于mx,则必须重新自己算  
                p[i] = 1;    
            while(str[i - p[i]] == str[i + p[i]])  //算出回文字符串的半径  
                p[i]++;    
            if(p[i] + i > mx){  //记录目前回文字符串扩展最长的id  
                mx = p[i] + i;    
                id = i;    
            }    
        }    
    }    


    int main(int argc, char const *argv[]){    

        while(scanf("%s",s) != EOF){    
            int n = pre();    
            manacher(n);    
            int ans = 0,i;    
            for(i = 1;i < n;i++)    
                if(p[i] > ans)    
                    ans = p[i];    
            printf("%d\n",ans - 1);         
        }    
        return 0;    
    }   

上面的程序说明:pre()函数对给定字符串进行预处理,也就是加分隔符。

上面几个变量说明:id记录具有遍历过程中最长半径的回文字符串中心字符串。mx记录了具有最长回文字符串的右边界。看下面这个图(注意,j为i关于id对称的点,j = 2*id - i):
这里写图片描述

但是p[i] = p[j]是没有错的,但是这里有个问题,就是i的一部分超出阴影部分,这就不对了。请看下图(为了看得更清楚,下面子串用细条纹表示):
这里写图片描述

此时,根据对称型只能得出p[i]和p[j]红色阴影部分是相等的,这就为什么有取最小值这个操作:

   if(mx > i)  //在这个之类可以借助前面算的一部分  
        p[i] = min(mx - i,p[2 * id - i]);  

下面代码就很容易看懂了。

最后遍历一遍p数组,找出最大的p[i]-1就是所求的最长回文字符串长度,下面证明一下:
(1)因为p[i]记录插入分隔符之后的回文字符串半径,注意插入分隔符之后的字符串中的回文字符串肯定是奇数长度,所以以i为中心的回文字符串长度为2*p[i]-1。

例如:

bb=>#b#b#
bab=>#b#a#a#b#

2)注意上面两个例子的关系。#b#b#减去一个#号的长度就是原来的2倍。即((2*p[i]-1)-1)/2 = p(i)-1,得证。

算法的有效比较次数为MaxId 次,所以说这个算法的时间复杂度为O(n)。

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

智能推荐

剑指offer 合并两个排序的链表

题目 链接:https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/ 思路 我想的是,与合并两个有序数组一样的思维,新建一个链表,然后判断谁的值大,进而在新的链表上面进行插入。 看书思路 合并链表是一个递归问题:合并一个节点后可以转化为一个子问题。终止条件是其中一个链表为空 代码 链表反转也可以用递归解决...

Java编程思想 第三章:操作符

Java中的操作符和c/c++中的操作符基本一致,因为我之前学习过C语言和C++,所以本章的内容大部分都已熟知,下面只做简单的介绍。 Java操作符及优先级 Java中的操作符包括算术操作符,关系操作符,逻辑操作符,位运算符、自操作运算符、移位运算符、赋值运算符和其他运算符。 算术操作符:包括加减乘除和取余(%),优先级乘除取余高于加减,都是双元运算符,其中加法(+)可以用来连接两个字符串,比如:...

JetBrains 系列开发工具,如何配置 `SCSS` `File Watcher` ,相关输出配置参数详解:webStorm phpStorm IDEA

JetBrains 系列开发工具,如何配置 SCSS File Watcher ,相关输出配置参数详解:webStorm phpStorm IDEA 前言 你目前已经了解了如何使用 SCSS 进行开发,了解了该文章的内容:『 SCSS 日常用法 』 在 JetBrains 系列开发工具中通过 FileWatcher 进行编译的 SCSS 文件都是通过 sass 这个程序进行的。『 如何添加 Fil...

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 - ...