首页 > 代码库 > [HDU3068]最长回文
[HDU3068]最长回文
[HDU3068]最长回文
试题描述
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等
回文就是正反读都是一样的字符串,如aba, abba等
输入
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000
输出
每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.
输入示例
aaaa
abab
输出示例
4 3
数据规模及约定
见“输入”
题解
学习了一下 manacher 算法,O(n) 求出以每个位置为中心的最长回文串长度,这个算法主要利用了“若回文串前半部分的某个子串是回文串,那么它的后半部分对应位置的子串是一模一样的回文串”,详情请百度,随便找一个博客上都解释得很清楚。
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <stack> #include <vector> #include <queue> #include <cstring> #include <string> #include <map> #include <set> using namespace std; #define maxn 220010 char Str[maxn], S[maxn]; int Len[maxn], alp[maxn]; int main() { while(scanf("%s", Str + 1) == 1) { int n = strlen(Str + 1); for(int i = 1; i <= n; i++) S[(i<<1)-1] = Str[i], S[i<<1] = ‘#‘; n <<= 1; n--; for(int i = 1; i <= n; i++) alp[i] = alp[i-1] + (‘a‘ <= S[i] && S[i] <= ‘z‘); int mxi = 0, ans = 0; for(int i = 1; i <= n; i++) { int mxp = mxi + Len[mxi] - 1; if(mxp < i) Len[i] = 1; else Len[i] = min(Len[(mxi<<1)-i], mxp - i + 1); while(1 <= i - Len[i] + 1 && i + Len[i] - 1 <= n && S[i-Len[i]+1] == S[i+Len[i]-1]) Len[i]++; Len[i]--; if(mxp < i + Len[i] - 1) mxi = i; int l = i - Len[i] + 1, r = i + Len[i] - 1; ans = max(ans, alp[r] - alp[l-1]); } printf("%d\n", ans); } return 0; }
[HDU3068]最长回文
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。