网站元素优化 移动站,个人网站开发实例,comsenzexp wordpress,服务周到的网站建站P4555 [国家集训队] 最长双回文串 思路
写这个题主要是为了练习manacher算法#xff0c;当然也有很多其他的方法可以做。 注意到题目要求找的是两个回文串拼起来#xff0c;而manacher算法刚好能计算出以每个位置为中心的最长回文子串。 这种左右两边拼接的问题考虑枚举分断…P4555 [国家集训队] 最长双回文串 思路
写这个题主要是为了练习manacher算法当然也有很多其他的方法可以做。 注意到题目要求找的是两个回文串拼起来而manacher算法刚好能计算出以每个位置为中心的最长回文子串。 这种左右两边拼接的问题考虑枚举分断点。在manacher算法的过程中顺便维护每个位置作为左右端点的最长回文子串长度用lbrb数组维护然后枚举分断点统计最大ans
代码
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define endl \n
#define int long long
#define pb push_back
#define pii pairint, int
#define FU(i, a, b) for (int i (a); i (b); i)
#define FD(i, a, b) for (int i (a); i (b); --i)
const int MOD 1e9 7;
const int INF 0x3f3f3f3f;
const int maxn 3e5, MAXN maxn;
string getns(string s) {string ns $#;for (int i 0; i s.size(); i) {ns s[i];ns #;}ns ^;return ns;
}
int d[maxn];
int rb[maxn], lb[maxn];
void manacher(string s) {int l 0, r 0, ans 0;for (int i 1; i s.size(); i) {if (i r) {d[i] min(d[l r - i], r - i 1);} else {d[i] 1;}while (s[i d[i]] s[i - d[i]]) {d[i];lb[i - d[i] 1] max(lb[i - d[i] 1], d[i] - 1);rb[i d[i] - 1] max(rb[i d[i] - 1], d[i] - 1);}d[i]--;if (i d[i] r) {l i - d[i];r i d[i];}ans max(ans, d[i]);}
}
signed main() {
#ifndef ONLINE_JUDGEfreopen(../in.txt, r, stdin);
#endifcin.tie(0)-ios::sync_with_stdio(0);string s;cin s;string ns getns(s);manacher(ns);int ans 0;// coutnsendl;FU(i, 0, ns.size()) {// coutlb[i] rb[i]endl;if (lb[i] ! 0 rb[i] ! 0) // 注意不能是单边的情况ans max(ans, lb[i] rb[i]);}cout ans endl;return 0;
}
