新建网站怎么做优化,free wordpress,wordpress widget修改,论文中小企业的网站建设双倍回文
金牌导航 manacher-2
luogu 4287
题目大意
设串为x#xff0c;将其取反为x’#xff0c;定义双倍回文为形如xx’xx’的串 现在给你一个字符串#xff0c;让你求最大双倍回文子串
输入样例
16
ggabaabaabaaball输出样例
12数据范围 N⩽105N\leqslant 10^5N⩽…双倍回文
金牌导航 manacher-2
luogu 4287
题目大意
设串为x将其取反为x’定义双倍回文为形如xx’xx’的串 现在给你一个字符串让你求最大双倍回文子串
输入样例
16
ggabaabaabaaball输出样例
12数据范围
N⩽105N\leqslant 10^5N⩽105
解题思路
对于该字符串可以用manacher求回文子串在求回文子串的同时判断是否双倍回文 对于通过对称得到最小回文长度的因为对称所以不用判断 对于字符判断使其回文长度增加的每增加一次就判断一次 这样就可以得到最大双倍回文子串长度了
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 1000050
using namespace std;
int n, p, mx, ans, v[N];
char s[N];
string str;
int main()
{scanf(%d, n);cinstr;s[0] /;s[1] #;for (int i 1; i n; i)s[i * 2] str[i - 1], s[i * 2 1] #;s[n * 2 2] |;n n * 2 1;p 1;mx 1;for (int i 1; i n; i){if (i mx) v[i] min(v[p * 2 - i], mx - i);//对称就不用判断了else v[i] 1;while(s[i - v[i]] s[i v[i]]){v[i];if (i1 v[i] % 4 0 v[i - v[i] / 2] - 1 v[i] / 2)//判断是否符合双倍回文ans max(ans, v[i]);//因为有‘#’乘除2就抵消了}if (i v[i] mx){mx i v[i];p i;}}printf(%d, ans);return 0;
}
