题目
题目描述
小A非常喜欢回文串，当然我们都知道回文串这种情况是非常特殊的。所以小A只想知道给定的一个字符串的最大回文子串是多少，但是小A对这个结果并不是非常满意。现在小A可以对这个字符串做一些改动，他可以把这个字符串最前面的某一段连续的字符(不改变顺序)移动到原先字符串的末尾。那么请问小A通过这样的操作之后(也可以选择不移动)能够得到最大回文子串的长度是多少。
输入描述
一行一个字符串表示给定的字符串S一行一个字符串表示给定的字符串S一行一个字符串表示给定的字符串S
输出描述
一行输出一个整数，表示通过这样的操作后可以得到最大回文子串的长度。
示例1
输入
dcbaabc
输出
7
说明
将前面的dcba移动到末尾变成abcdcba，这个字符串的最大回文子串就是它本身，长度为7
备注
表示字符串的长度，\(1 \leq N \leq 5000\)
题解
知识点：区间dp。
这是一道环状处理的区间dp，但注意，如果不加以优化直接加倍会产生 \(10^8\) 大小的数组会炸空间。
注意到题目要求处理的是回文子串，因此 \(dp[i][j]\) 本身直接代表是否是回文串即可。
又区间dp是按照长度为阶段进行的，因此知道一个端点就能知道另一个；同时回文子串的判断只可能从长度减 \(2\) 的地方传递过来，其他长度的用不到了，所以只需要保存前两次长度对应的所有区间信息即可。
有了这两个条件（缺一不可）我们可以去掉一维换成长度，即 \(dp[i][j]\) 为以 \(i\) 为左端点，区间长度模 \(3\) 为 \(j\) 的区间是否是回文串，循环存储信息即可，这样就能做了，细节上看代码。
时间复杂度 \(O(n^2)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
bool dp[5007 << 1][3];///左端点，长度
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
string s;
cin >> s;
int n = s.size();
s += s;
for (int i = 0;i < 2 * n;i++) dp[i][0] = dp[i][1] = 1;
int ans = 1;
for (int l = 2;l <= n;l++) {
for (int i = 0, j = l - 1;j < 2 * n;i++, j++) {
if (s[i] == s[j] && dp[i + 1][(l + 1) % 3]) dp[i][l % 3] = 1;
else dp[i][l % 3] = 0;///调零
if (dp[i][l % 3]) ans = max(ans, l);
}
}
cout << ans << '\n';
return 0;
}