C++ 算法：字符串蜈蚣 - 寻找最长回文子串

"C++ 算法：字符串蜈蚣 - 寻找最长回文子串"\n\n小榔被困在地宫，需要通过层层关卡才能回到地面。他利用自己的聪明才智已经来到了地宫的第 98 层，这里守护者是一只字符串蜈蚣。为了打败字符串蜈蚣，小榔需要说出该字符串中最长的回文子串的长度。\n\n现在给定一个字符串，请你帮助小榔计算这个字符串中最长的回文子串的长度，让他顺利到达地宫的第 97 层。\n\n输入\n第一行：一个整数 n，表示字符串的长度。\n第二行：包含一个字符串，由大写字母和小写字母组成。\n\n输出\n第一行：一个整数，表示该字符串最长的回文子串的长度。\n\n输入样例 1\n12\nabaABCDCBAcb\n输出样例 1\n7\n\n提示\n【输入输出样例 1 说明】\n最大的回文字串为 "ABCDCBA"，长度为 7。\n\n【数据规模与约定】\n对于 100% 的数据：n<=400; \n\n思路：\n1. 遍历字符串中的每个字符，以每个字符为中心，分别向左右两边扩展，查找回文子串。记录最长的回文子串的长度。\n2. 遍历字符串中的每个字符，以每个字符和下一个字符的间隙为中心，分别向左右两边扩展，查找回文子串。记录最长的回文子串的长度。\n3. 输出最长回文子串的长度。\n\n代码实现：\ncpp\n#include <iostream>\n#include <string>\nusing namespace std;\n\nint findLongestPalindrome(string s) {\n int maxLength = 1; // 最长回文子串的长度\n int n = s.length();\n \n // 以每个字符为中心，查找回文子串\n for (int i = 0; i < n; i++) {\n int left = i - 1;\n int right = i + 1;\n while (left >= 0 && right < n && s[left] == s[right]) {\n int len = right - left + 1;\n if (len > maxLength) {\n maxLength = len;\n }\n left--;\n right++;\n }\n }\n \n // 以每个字符和下一个字符的间隙为中心，查找回文子串\n for (int i = 0; i < n - 1; i++) {\n int left = i;\n int right = i + 1;\n while (left >= 0 && right < n && s[left] == s[right]) {\n int len = right - left + 1;\n if (len > maxLength) {\n maxLength = len;\n }\n left--;\n right++;\n }\n }\n \n return maxLength;\n}\n\nint main() {\n int n;\n cin >> n;\n string s;\n cin >> s;\n \n int maxLength = findLongestPalindrome(s);\n cout << maxLength << endl;\n \n return 0;\n}\n\n\n复杂度分析：\n- 时间复杂度：O(n^2)，其中 n 为字符串的长度。遍历字符串需要 O(n) 的时间，每次查找回文子串的时间复杂度为 O(n)，总共需要进行 O(n) 次查找。\n- 空间复杂度：O(1)。只使用了常数个额外的变量。