1. 暴力

时间复杂度O(n^3)。

2. 延展

以某一字符为中心,设置left, right两个变量同时向外扩,判断他们指向字符是否相同。注意分奇偶讨论。时间复杂度O(n^2)。

3. Manacher 马拉车

代码注释:

 1 const int MAXN = 110009;
2 char ma[MAXN * 2]; //因为要添加'#',所以长度要开两倍
3 int mp[MAXN * 2];
4 char s[MAXN];
5
6 void Manacher(char s[], int len) {
7
8 // 1. 构造字符串,添加'#',使长度变为奇数(2 * len - 1)
9 int l = 0;
10 ma[l++] = '$'; // 设置边界
11 ma[l++] = '#';
12 for(int i = 0; i < len; i ++) {
13 ma[l++] = s[i];
14 ma[l++] = '#';
15 }
16 ma[l] = 0;
17
18 // 核心: 求回文半径, 回文半径包括中心点
19 int mx = 0; // mx代表可达的最右值
20 int id = 0; // id代表mx的中心
21 for(int i = 0; i < l; i ++) {
22 mp[i] = mx > i ? min(mp[2 * id - i], mx - i) : 1;
23 while(ma[i + mp[i]] == ma[i - mp[i]]) {
24 mp[i] ++;
25 }
26 if(i + mp[i] > mx) {
27 mx = i + mp[i];
28 id = i;
29 }
30 }
31
32 }
33
34 int main()
35 {
36
37 while(scanf("%s", s) != EOF) {
38 int len = strlen(s);
39 Manacher(s, len);
40 int ans = 0;
41 for(int i = 0; i < 2 * len + 2; i ++) { // 寻找最长的回文半径,即回文串长度
42 ans = max(ans, mp[i] - 1); // 回文半径减1就是原回文串的长度(回文半径中虚加了#)
43 cout << mp[i] << " ";
44 }
45 printf("%d\n", ans);
46 }
47
48 return 0;
49 }

时间复杂度O(n)。

判断最长回文串——暴力、延展、Manacher的更多相关文章

  1. Manacher算法 - 求最长回文串的利器

    求最长回文串的利器 - Manacher算法 Manacher主要是用来求某个字符串的最长回文子串. 不要被manacher这个名字吓倒了,其实manacher算法很简单,也很容易理解,程序短,时间复 ...

  2. Longest Palindrome 最长回文串问题

    1.题目 Given a string s, find the longest palindromic substring in s. You may assume that the maximum ...

  3. 算法 -- 四种方法获取的最长“回文串”,并对时间复杂进行分析对比&amp;PHP

    https://blog.csdn.net/hongyuancao/article/details/82962382 “回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就 ...

  4. MANACHER---求最长回文串

    求最长回文串,如果是暴力的方法的话,会枚举每个字符为中心,然后向两边检测求出最长的回文串,时间复杂度在最坏的情况下就是0(n^2),为什么时间复杂度会这么高,因为对于每一个作为中心的字符的检测是独立的 ...

  5. 字符串的最长回文串:Manacher’s Algorithm

    题目链接:Longest Palindromic Substring 1. 问题描述 Given a string S, find the longest palindromic substring ...

  6. Leetcode0005--Longest Palindromic Substring 最长回文串

    [转载请注明]http://www.cnblogs.com/igoslly/p/8726771.html 来看一下题目: Given a string s, find the longest pali ...

  7. Manacher模板(O(n)内求最长回文串长度)

    转自:https://segmentfault.com/a/1190000008484167 /* 由于回文分为偶回文(比如 bccb)和奇回文(比如 bcacb),而在处理奇偶问题上会比较繁琐,所以 ...

  8. ACM题目————最长回文串

    Description 给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba, abba等   Input 输入有多组cas ...

  9. Manacher&#39;s Algorithm 马拉车算法(求最长回文串)

    作用:求一个字符串中的最长子串,同时还可以求所有子串的长度. 题目链接: https://vjudge.net/contest/254692#problem/B 最长回文串长度的代码: int Man ...

  10. (最长回文串 模板) 最长回文 -- hdu -- 3068

    http://acm.hdu.edu.cn/showproblem.php?pid=3068 最长回文 Time Limit: 4000/2000 MS (Java/Others)    Memory ...

随机推荐

  1. 多线程编程-工具篇-BlockingQueue

    在新增的Concurrent包中,BlockingQueue很好的解决了多线程中,如何高效安全"传输"数据的问题.通过这些高效并且线程安全的队列类,为我们快速搭建高质量的多线程程序 ...

  2. JavaWeb学习笔记——第一个JSP文件

    必须加上第一句以用来指定编码,否则会出现乱码 <%@ page language="java" import="java.util.*" contentT ...

  3. Nodejs中cluster模块的多进程共享数据问题

    Nodejs中cluster模块的多进程共享数据问题 前述 nodejs在v0.6.x之后增加了一个模块cluster用于实现多进程,利用child_process模块来创建和管理进程,增加程序在多核 ...

  4. shell脚本定时操作数据库

    一.数据库脚本(mysql.sh) Linux环境下,定时将数据库A的表格复制到数据库B中 #!/bin/bash mysql_host="127.0.0.1" mysql_use ...

  5. 【转载】Mysql binlog relaylog 日志迁移

    背景:   默认情况下,mysql的数据.binlog.relaylog都是保存在同一个磁盘上,路径根据每个人的设置不一. 当mysql数据库中数据或日志增长很快时,磁盘可能面临空间不够或者IO性能跟 ...

  6. 抽奖转盘(jqueryrotate.js)

    jqueryrotate.js抽奖转盘,使用方便,兼容各浏览器,效果如下图 <!DOCTYPE> <head> <meta http-equiv="Conten ...

  7. postman - 基本操作

    设置环境 collections 导入 runner 导入 api 配置api 编写测试(请求和响应)脚本 api的保存和导出 setting file -- setting

  8. JS面向对象与面向过程

    前言 面向对象编程: 就是将你的需求抽象成一个对象,然后针对这个对象分析其特征(属性)与动作(方法)--这个对象就称之为类 面向过程编程: 特点:封装,就是将你需要的功能放在一个对象里面 ------ ...

  9. nginx rewrite (转发)

    1.location正则写法 一个示例: location = / { # 精确匹配 / ,主机名后面不能带任何字符串 [ configuration A ] } location / { # 因为所 ...

  10. 我的C++ 学习心得

    创建这个博客已经是我大一下学期的暑假了,这一年里,我学习了人生第一门编程语言C++ . C++是一门当前仍然活跃于开发前沿的编程语言.在还未开始正式学习它时,早就听到我们的学长抱怨C++难学.起初,我 ...