东莞网站优化制作,谷雨网页设计作业,网页设计心得体会结尾,设计logo网站免费无水印题干#xff1a;
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba, abba等
Input
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S 两组case之间由空行隔开(该空行不用…题干
给出一个只由小写英文字符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
aaaaabab
Sample Output
4
3
解题报告 裸的马拉车算法一定注意修改后的数组需要开二倍就好了不然会RE但是我也不知道为什么HDUoj报TLE很迷。。但是这题好像可以暴力啊。。跑出来都是200多ms。。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
int top;
char s[110005],str[1100051];
int p[1200051];
int manacher() {if(top 0) return 0 ;int maxx -1;int c -1,r -1;for(int i 1; itop; i) {p[i] ri ? min(p[2*c-i],r-i) : 1;
// while(ip[i]top i-p[i] -1) {
// if(str[ip[i]] str[i-p[i]]) p[i];
// else break;
// }for(;str[i-p[i]] str[ip[i]];p[i]);if(ip[i] r) {r ip[i];ci;}maxx max(maxx,p[i]);}return maxx-1;
}
int main()
{while(~scanf(%s,s)) {int len strlen(s);top0;str[top] ;for(int i 0; ilen; i) {str[top] #;str[top] s[i];}str[top] #;str[top] \0;
// printf(%s\n,str);printf(%d\n,manacher());} return 0 ;}
