江西城乡建设网站,百度怎么收录我的网站,网站建设平台天梯建站网站建投网站,seo网站运营正题
luogu 4555 题目大意
给出一个字符串#xff0c;让你求两个相邻的回文串的最大长度和 解题思路
先用Manacher求出最长回文串
然后暴力配对即可 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define l…正题
luogu 4555 题目大意
给出一个字符串让你求两个相邻的回文串的最大长度和 解题思路
先用Manacher求出最长回文串
然后暴力配对即可 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 200021
using namespace std;
int n, ans, l[N], r[N], v[N], s[N];
string str;
void Manacher()
{int mid 0, mx 0;for (int i 1; i n; i){if (i mx) v[i] min(v[mid * 2 - i], mx - i);else v[i] 1;while(s[i v[i]] s[i - v[i]]) v[i];if (i v[i] mx){mx i v[i];mid i;}r[i - v[i] 1] max(r[i - v[i] 1], v[i] - 1);//存下以某个点为左端的最大回文串l[i v[i] - 1] max(l[i v[i] - 1], v[i] - 1);}return;
}
int main()
{cinstr;n str.size();s[0] s[1] #;for (int i 1; i n; i){s[i * 2] str[i - 1];s[i * 2 1] #;}n n * 2 2;s[n] 0;Manacher();for (int i 2; i n; i){r[i] max(r[i], r[i - 2] - 2);//减少一个长度if (l[i] r[i]) ans max(ans, l[i] r[i]);}printf(%d, ans);return 0;
}
