hdu3068 求一个字符串中最长回文字符串的长度 Manacher算法

最长回文

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 31611    Accepted Submission(s): 11618

Problem Description

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

Input

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000

Output

每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

Sample Input

aaaa

abab

Sample Output

4

3

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
//最长回文,Manacher算法
char s[211000],c[111000];//注意S数组的大小至少要开C数组的两倍
int p[211000];//P可以理解为回文字符串的半径

void init()//初始化S数组
{
    int i,j;
    s[0]=‘@‘;
    for(i=0;c[i]!=0;i++)
    {
        s[2*i+1]=‘#‘;
        s[2*i+2]=c[i];
    }
    s[2*i+1]=‘#‘;
    s[2*i+2]=0;
}
int manacher()
{
    int id=0,mx=0,i;
    for(i=1;s[i]!=0;i++)
    {
        if(mx>i)
        p[i]=min(p[2*id-i],mx-i);
        else
        p[i]=1;
        //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;
        }
    }
    mx=0;
    for(i=1;s[i]!=0;i++)
    {
        if(p[i]>mx)
        mx=p[i];
    }
    return mx-1;
}
int main()//用cin\cout 会超时
{
    while(~scanf("%s",c))
    {
        init();
        printf("%d\n",manacher());
    }
    return 0;
}

原文地址:https://www.cnblogs.com/-citywall123/p/10034374.html

时间: 11-28

hdu3068 求一个字符串中最长回文字符串的长度 Manacher算法的相关文章

hdu 3068 最长回文串 o(n) Manacher 算法

最长回文 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10596    Accepted Submission(s): 3759 Problem Description 给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba, abba等 Input 输入有多

求一个字串中最长的连续字符串

举例子来说:对于字符串"1234abcdef1234567abcdefghijklmn",这个字串中最长的连续字符串为"abcdefghijklmn". int continumax(char *outputstr,char *inputstr) { char maxrecord[100] = {0}; int maxlength = 0; char currentrecord[100] = {0}; int currentlength = 0; char valu

计算字符串的最长回文子串 :Manacher算法介绍

在介绍算法之前,首先介绍一下什么是回文串,所谓回文串,简单来说就是正着读和反着读都是一样的字符串,比如abba,noon等等,一个字符串的最长回文子串即为这个字符串的子串中,是回文串的最长的那个. 计 算字符串的最长回文字串最简单的算法就是枚举该字符串的每一个子串,并且判断这个子串是否为回文串,这个算法的时间复杂度为O(n^3)的,显然无法令人 满意,稍微优化的一个算法是枚举回文串的中点,这里要分为两种情况,一种是回文串长度是奇数的情况,另一种是回文串长度是偶数的情况,枚举中点再判断是否 是回文

Longest Substring Without Repeating Characters 字符串中最长的无重复子串长度

Longest Substring Without Repeating Characters Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the lengt

最长回文字符串 POJ3974

曾经有一个好算法放到我面前,我没有好好珍惜,直到用到的时候才后悔莫及. 那就是Manacher(马拉车算法),以O(n)的复杂度计算最长回文字符串. 曾经刷Leetcode的时候,室友跟我说了这个算法,但当时那个题目用中间枚举也过了,我就没有在意,直到前天才弄会,写这篇报告之前, 我又专门写了一遍马拉车,果然还是有点问题的. 详细原理链接 点击 Mark #include <stdio.h> #include <iostream> #include <string.h>

URAL 1297 求最长回文字符串

有种简单的方法,数组从左到右扫一遍,每次以当前的点为中心,只要左右相等就往左右走,这算出来的回文字符串是奇数长度的 还有偶数长度的回文字符串就是以当前扫到的点和它左边的点作为中心,然后往左右扫 这是O(n^2)的复杂度,这道题过还是没有问题的 这里我主要练习的是另外的利用后缀数组加RMQ算法来解决这个问题 大致思想跟上面一致 首先将字符串反转贴在原字符串末尾,将字符通过ASCII码转化为字符,之间用一个1分开,最后贴一个0 然后得到它的后缀数组以及height[]数组 那么找回文字符也是扫一遍,

csu-1328 近似回文词 和 最长回文字符串

原博文地址:http://blog.csdn.net/u012773338/article/details/39857997 最长回文子串 描述:输入一个字符串,求出其中最长的回文子串.子串的含义是:在原串连续出现的字符 串片段.回文的含义是:正着看和倒着看是相同的,如abba和abbebba.在判断是要求忽略所有的标点和空格,且忽略大小写,但输出时按原样输出(首 尾不要输出多余的字符串).输入字符串长度大于等于1小于等于5000,且单独占一行(如果有多组答案,输出第一组). 输入 :每行有一个

Java Longest Palindromic Substring(最长回文字符串)

假设一个字符串从左向右写和从右向左写是一样的,这种字符串就叫做palindromic string.如aba,或者abba.本题是这种,给定输入一个字符串.要求输出一个子串,使得子串是最长的padromic string. 下边提供3种思路 1.两側比較法 以abba这样一个字符串为例来看,abba中,一共同拥有偶数个字.第1位=倒数第1位.第2位=倒数第2位......第N位=倒数第N位 以aba这样一个字符串为例来看,aba中.一共同拥有奇数个字符.排除掉正中间的那个字符后,第1位=倒数第1

409.求最长回文串的长度 LongestPalindrome

题目要求求出长度即可,并不需要求出最长回文串. 思路:用字典统计每一个字符的出现次数,出现次数大于1的字符必定出现在回文串中,另外还再加上一个中心点. public static int LongestPalindrome(string s) { int length = 0; Dictionary<char, int> dictionary = new Dictionary<char, int>(); int value = 0; foreach (char c in s) {

求最长回文字符串

暴力算法:o(n3) //暴力算法 public class LongestPalindrome { public String longestPalindrome(String s) { String sub = null; int len = 0; for(int i = 0; i < s.length(); i ++) { for(int j = i; j < s.length(); j ++) { String tmp = s.substring(i,j+1); if(isPalind