L2-008 最长对称子串 (25分)
对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。
输入格式：
输入在一行中给出长度不超过1000的非空字符串。
输出格式：
在一行中输出最长对称子串的长度。
输入样例：
Is PAT&TAP symmetric?
输出样例：
11
思路一
由于字符串长仅1000，可以选择直接暴力找
思路二
套一下马拉车算法的模板即可
算法讲解：Here
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
string s;
char s_new[4000];
int p[5000];
int Init() {
int len = s.length();
s_new[0] = '$';
s_new[1] = '#';
int j = 2;
for (int i = 0; i < len; i++) {
s_new[j++] = s[i];
s_new[j++] = '#';
}
s_new[j] = ' '; // 别忘了哦
return j; // 返回 s_new 的长度
}
int Manacher() {
int len = Init(); // 取得新字符串长度并完成向 s_new 的转换
int max_len = -1; // 最长回文长度
int id;
int mx = 0;
for (int i = 1; i < len; i++) {
if (i < mx)
p[i] = min(p[2 * id - i],
mx - i); // 需搞清楚上面那张图含义, mx 和 2*id-i 的含义
else
p[i] = 1;
while (s_new[i - p[i]] ==
s_new[i + p[i]]) // 不需边界判断，因为左有'$',右有' '
p[i]++;
// 我们每走一步 i，都要和 mx 比较，我们希望 mx
// 尽可能的远，这样才能更有机会执行 if (i < mx)这句代码，从而提高效率
if (mx < i + p[i]) {
id = i;
mx = i + p[i];
}
max_len = max(max_len, p[i] - 1);
}
return max_len;
}
int main() {
getline(cin, s);
printf("%d
", Manacher());
return 0;
}
思路三
没想到可以使用DP做，思路来自网络
动态规划：
分析：有两种可能，⼀种是回⽂字符串的⻓度为奇数，⼀种是偶数的情况。i为字符串当前字符的下 标。
当回⽂字串为奇数的时候，j表示i-j与i+j构成的回⽂字串⻓度；当回⽂字串⻓度为偶数的时候，j表示
i+1左边j个字符⼀直到i右边j个字符的回⽂字串⻓度～
⽤maxvalue保存遍历结果得到的最⼤值并且输出～
#include <iostream>
using namespace std;
int main() {
string s;
getline(cin, s);
int maxvalue = 0, temp;
int len = s.length();
for (int i = 0; i < len; i++) {
temp = 1;
for (int j = 1; j < len; j++) {
if (i - j < 0 || i + j >= len || s[i - j] != s[i + j])
break;
temp += 2;
}
maxvalue = temp > maxvalue ? temp : maxvalue;
temp = 0;
for (int j = 1; j < len; j++) {
if (i - j + 1 < 0 || i + j >= len || s[i - j + 1] != s[i + j])
break;
temp += 2;
}
maxvalue = temp > maxvalue ? temp : maxvalue;
}
cout << maxvalue;
return 0;
}