51Nod_1089 最长回文子串 V2（Manacher算法）

本文主要是介绍51Nod_1089 最长回文子串 V2（Manacher算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

                    51Nod_1089 最长回文子串 V2（Manacher算法）

                                http://www.51nod.com/Challenge/Problem.html#!#problemId=1089

 

题目

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。输入一个字符串Str，输出Str里最长回文子串的长度。

输入

输入Str（Str的长度 <= 100000)

输出

输出最长回文子串的长度L。

样例输入

daabaac

样例输出

5

C++程序

#include<iostream>
#include<string>
#include<cstring>using namespace std;const int N=100000;
int p[2*N+10];int LongestPalindrome(string s)
{if(s=="")return 0; int mx=0,id=0,end=s.length();memset(p,0,sizeof(p));for(int k=0;k<=end*2+1;k+=2)s.insert(k,"#");for(int i=0;s[i]!='\0';i++){p[i]=mx>i?min(p[2*id-i],mx-i):1;while((i+p[i]<s.length())&&(i-p[i]>=0)&&s[i+p[i]]==s[i-p[i]]) p[i]++;if(i+p[i]>mx){mx=i+p[i];id=i;}}int maxlen=1;for(int i=0;i<s.length();i++)if(maxlen<p[i])maxlen=p[i];return maxlen-1;
}int main()
{string s;getline(cin,s);cout<<LongestPalindrome(s)<<endl;return 0;
}

 

这篇关于51Nod_1089 最长回文子串 V2（Manacher算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---