文档章节

Manacher算法 线性时间求最大回文子串长度

YYQ_ZJL
 YYQ_ZJL
发布于 2016/07/03 10:34
字数 237
阅读 7
收藏 0

原理性的东西在这里得到:http://www.open-open.com/lib/view/open1419150233417.html

/*Manacher算法*/
#include<iostream>
#include<vector>
#include<map>
#include<stdio.h>
#define maxn 100000
#define min(a,b) a>b?b:a
#define max(a,b) a>b?a:b
using namespace std;
char str[maxn];       //元字符串
char tmp[2*maxn+1];   //转换后的字符串
int length;
int len[2*maxn+1];
void Get_New()
{
    int i,j;
    tmp[0]='@';                     //字符串开头增加一个特殊字符,防止越界
    for(i = 1;i <= 2*length;i += 2){
        tmp[i] = '#';
        tmp[i+1] = str[i/2];
    }
    tmp[2*length+1]='#';
}
int Manacher()
{
    int i;
    int mid,maxlen,ans;
    len[0] = 1;
    mid = ans = maxlen = 0;
    for(i = 1;i <= 2*length+1;i ++){
        if(maxlen > i){
            len[i] = min(maxlen-i,len[2*mid-i]);
        }
        else{
            len[i] = 1;
        }
        while(tmp[i-len[i]] == tmp[i+len[i]])
                len[i] ++;
        printf("len[%d] = %d ",i,len[i]);
        printf("\n");
        if(len[i] + i > maxlen){
            maxlen = len[i] + i;
            mid = i;
        }
        ans = max(ans,len[i]);
    }
    return ans - 1;
}
int main(void)
{
    int i,ans,pos;
    cin >>length;
    for(i = 0;i < length;i++)
        cin >> str[i];
    Get_New();
    ans = Manacher();
    cout <<ans <<endl;
    return 0;
}

 

本文转载自:http://www.cnblogs.com/zhangjialu2015/p/5262285.html

YYQ_ZJL
粉丝 0
博文 30
码字总数 206
作品 0
杭州
其他
私信 提问
Manacher's Algorithm 马拉车算法

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

机器的心脏
2017/12/02
0
0
最长回文子串与Manacher算法

题目描述 给定一个字符串,求它的最长回文子串的长度。 最简单粗暴的方法就是,枚举全部的字符串,然后每个都判断一下是不是回文,然后得到长度最长的字符串。显然,这个方法是可行的,可是也...

yejq8
2015/05/16
435
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
Manacher算法求解最长回文子串

一、背景 最近在LintCode上面刷题时遇到了一个求解最长回文子串的问题,这个题目可以使用暴力的方式去进行求解,但算法的时间复杂度至少就是O(n^2)级别了,后面看讨论区时发现了一个比较有意...

丶legend
2018/06/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CentOS 7 查找软件安装位置的方法

1、通过文件搜索查找 root@jun-virtual-machine:# find / -name "*squid*"/var/log/squid/var/spool/squid/var/lib/yum/yumdb/s/48a7dbee62d6d5962ed739a8e4fc117cf7378bfd-squid-3.5......

webcreazy
24分钟前
5
0
eureka 加入密码认证 springboot-admin 加入密码认证

1. pom.xml 加入依赖 <!-- 加入密码认证 --><dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-security</ar......

java框架开发者
27分钟前
4
0
数字在排序数组中出现的次数

Input:nums = 1, 2, 3, 3, 3, 3, 4, 6K = 3Output:4 二分查找的练习 public int GetNumberOfK(int[] nums, int K) { int first = binarySearch(nums, K); int last = b......

Garphy
39分钟前
5
0
大厂面试经:高频率JVM面试问题整理!

JVM(Java虚拟机)简单来说就是运行Java代码的解释器,作为螺丝钉程序员JVM其实了解下就差不多啦,不懂JVM内部细节照样能写出优质的代码!但是一到造火箭、飞机的场景(面试)不懂JVM的你,会...

架构文摘
54分钟前
9
0
thinkphp5.1学习过程五——request

<?phpnamespace app\index\controller;//use \think\facade\Request;use \think\Request;/** * Class Demo3 * @package app\index\controller * 正常情况下,控制器不依赖......

大海yht
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部