企业官网建设流程全解析

1. 题目拆解：L2-008到底在考什么

事情要从几天前说起。我在整理历年的天梯赛真题时，又把L2-008这道"最长对称子串"翻了出来。别看它在L2级别里不算最难的，但每次做都能踩出一点新东西，这次干脆把整个思考过程完整记录下来。

先说说这题在问什么。题目会给你一个字符串，字符串里什么字符都可能有——大写字母、小写字母、数字、空格、标点符号，让你求出这个字符串中最长的对称子串的长度。"对称子串"就是回文串，比如"level"、"12321"这类从头读和从尾读一样的连续子串。很多人第一反应是"这题不是很简单嘛，枚举一下就行"，但真正动手写的时候才会发现，坑全藏在细节里，尤其是当字符串里出现空格和标点的时候。

这道题的核心考点其实有两个层面。表层考的是对"子串连续"这个概念的理解，里层考的是对"回文串枚举中心"这个模型的熟练度。我见过不少人的第一版代码是这么写的：三层for循环，第一层枚举起点，第二层枚举终点，第三层判断这个区间是不是回文。这种暴力写法在字符串不长的时候确实能过，一旦测试数据里塞进几百上千个字符，时间复杂度O(n^3)直接原地爆炸。

更隐蔽的坑在输入处理。题目给的字符串是可能带空格的，这意味着你不能用cin >> s那种方式来读，一碰到空格就停了。必须用getline把整行读进来。很多第一次做这道题的人，本地测试的时候用"abcba"这种纯单词字符串，一切正常，提交上去就是答案错误，多半就是栽在这个输入处理上。

还有一类人容易想复杂。一看到"最长对称子串"就想上Manacher算法、后缀数组这些高级数据结构。并不是说这些不行，而是在PTA这个平台上，字符串长度一般不会特别夸张，动规或者中心扩展法已经完全够用。后面我会详细分析三种写法的取舍。

2. 三种写法的演进：暴力、动态规划与中心扩展的取舍

2.1 暴力枚举：为什么O(n^3)会超时

我们先把最直觉的写法摆出来看。枚举所有子串的起点i和终点j，然后检查s[i]到s[j]这一段是不是回文串。伪代码大概是这样的：

int ans = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (isPalindrome(s, i, j)) { ans = max(ans, j - i + 1); } } }

这里isPalindrome内部还要再来一层循环，从两边往中间扫。三层循环叠在一起，时间复杂度就是O(n^3)。假设字符串长度是1000，最坏情况要跑10亿次基本操作，在评测机上基本是卡着时间线过不去。有人会说："那我加个break优化一下，判断到不是回文就停"，但最坏情况下，所有字符都相同（比如"aaaaaa..."），每次判断都要走完整个区间，优化等于没有。

2.2 动态规划：思路清晰但空间要算清楚

动态规划是很多人学回文串问题时最先接触的正规解法。定义dp[i][j]表示从第i个字符到第j个字符这一段是不是回文串。转移方程很容易理解：

• 如果s[i]不等于s[j]，那么dp[i][j]直接是false；
• 如果s[i]等于s[j]，那么只需要看中间那段dp[i+1][j-1]是不是回文。但这里有个前提：中间段的长度不能太短。当j - i <= 2时，也就是区间长度只有1或2的时候，只要首尾相等就一定是回文，不需要参考中间状态。

代码写出来也很工整：

vector<vector<int>> dp(n, vector<int>(n, 0)); int ans = 1; for (int i = 0; i < n; i++) dp[i][i] = 1; for (int len = 2; len <= n; len++) { for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; if (s[i] == s[j]) { if (len == 2) dp[i][j] = 1; else dp[i][j] = dp[i+1][j-1]; } if (dp[i][j]) ans = max(ans, len); } }

这个解法的优点是思路直白，不容易出错。但代价是空间复杂度O(n^2)，如果字符串长度上万，二维数组就要开到上亿个元素，内存直接报警。在PTA这道题里字符串长度大概在1000左右，开一个bool类型的二维数组勉强能撑住，但说实话没必要。动态规划适合那种需要同时求出所有回文子串数量的场景，对于"只求最长长度"这个目标，它有冗余的计算。

2.3 中心扩展法：最贴合回文串本质的解法

中心扩展法的思路和回文串的定义完全绑定。回文串的本质是"关于某个中心对称"，那我们就枚举每一个可能的对称中心，然后往两边扩展，看能撑多长。

这里有个关键点:对称中心有两种情况。一种是奇数的回文串，中心落在某个具体字符上，比如"abcba"的中心是'c'；另一种是偶数的回文串，中心落在两个字符之间，比如"abba"的中心在'b'和'b'之间。所以枚举中心的时候要分两条路走：

• 以当前字符为中心，向左右扩展，处理奇数长度的回文；
• 以当前字符和下一个字符的间隙为中心，向左右扩展，处理偶数长度的回文。

枚举一个中心，扩展的过程是O(n)的，而中心一共有2n-1个（n个字符中心加n-1个间隙中心），所以总时间复杂度是O(n^2)。这个复杂度在PTA这类平台上绰绰有余，而且空间复杂度只有O(1)。

我后来在实际测试中发现，中心扩展法不仅代码量最少，调起来也最轻松。对比三种写法，暴力法最直觉但最容易超时，动态规划最规范但空间有冗余，中心扩展法在本题的数据范围下是综合最优的选择。

3. 中心扩展法落地：完整代码与每一行细节

直接给出我最终提交通过的代码，用的是C++：

#include <iostream> #include <string> #include <algorithm> using namespace std; int main() { string s; getline(cin, s); int n = s.size(); int ans = 0; // 枚举每一个字符中心，处理奇数长度的回文串 for (int i = 0; i < n; i++) { int left = i, right = i; while (left >= 0 && right < n && s[left] == s[right]) { ans = max(ans, right - left + 1); left--; right++; } } // 枚举每一个间隙中心，处理偶数长度的回文串 for (int i = 0; i < n - 1; i++) { int left = i, right = i + 1; while (left >= 0 && right < n && s[left] == s[right]) { ans = max(ans, right - left + 1); left--; right++; } } cout << ans << endl; return 0; }

先看getline(cin, s)这行。题目字符串可能包含空格，用cin >> s只会读到第一个空格之前的内容，后面的全丢了。比如输入Is PAT&TAP symmetric?，用cin读到的就是"Is"，后面全没了，答案自然是错的。getline会一口气把包含空格的整行读进来，注意它也会把行尾的换行符读掉，但不会把换行符存进字符串里，这一点不用担心。

再看不含using namespace std的写法，如果坚持不用这个命名空间，写成std::string s; std::getline(std::cin, s);也可以，但竞赛里没必要和自己较劲，用了省事。

第一个for循环里，left = i; right = i;是把中心定位在第i个字符上。while循环的条件有三个：left >= 0防止左边界越界，right < n防止右边界越界，s[left] == s[right]判断两边字符是否相等。每成功匹配一对，就更新一次ans，然后左右指针同时向外扩一步。

第二个for循环处理偶数长度的情况。中心在i和i+1之间的间隙上，所以初始left = i; right = i + 1;。其余逻辑完全一样。

有一个细节值得注意：ans初始值应该设成多少？如果字符串为空，n为0，两个for循环都不会执行，ans还是0，输出0，这正好符合空串没有对称子串的语义。但如果题目保证字符串非空，也可以初始化为1，因为单个字符本身就是长度为1的对称子串。我是习惯初始化为0的，这样逻辑上更严谨，反正后面循环会把所有长度都更新进来。

另外，我见过有人在这道题里把两个for循环合并成一个，用"奇数中心往左往右各走一步"和"偶数中心往左走一步往右走两步"来区分，代码是短了，但可读性下降很多。竞赛代码虽然不追求可维护性，但清晰的代码能帮你减少调试时间，这在我看来比省几行更重要。

4. 边界条件与评测机行为：输入、输出与极端样例

4.1 样例输入实测：Is PAT&TAP symmetric?

题目给的经典样例是Is PAT&TAP symmetric?，注意这里"PAT&TAP"本身是一个回文串，长度为7。但如果我把前后都往外扩，会发现"空格PAT&TAP空格"也是回文，长度为9。再往外扩，左边是s，右边是s，又相等，所以"s空格PAT&TAP空格s"整个就是回文，长度为11。答案是11，和题目给出的输出一致。

这个样例特别能说明问题：对称子串没有必要以字母开头或结尾，空格和标点符号完全可以包含在回文串内部，只要左右对称即可。很多人手里有算法，但读题不仔细，以为标点和空格不能算在对称子串里，结果答案差了那么几个字符。

4.2 全同字符字符串的性能压力

如果输入是"aaaaaaaaaa..."，1000个'a'，整个字符串就是回文串，答案应该是1000。这种情况对中心扩展法有什么影响？

对每个中心，while循环都会一直扩展到字符串边界才停，每个中心平均扩展大约n/2次，总操作量大约是O(n^2)的常数倍。在这个数量级下，1000个字符的运行时间几乎可以忽略不计。但如果你用的是暴力O(n^3)写法，这种测试用例直接把运行时间拉满。所以如果你写完暴力的版本，别的样例都能过，只有全同字符的大数据超时，那基本可以断定是复杂度的问题而不是代码逻辑的问题。

还有个更隐蔽的极端情况：输入只有一个字符，比如"a"。第一个for循环里，以这个字符为中心，左右都相等（其实就是它自己），ans = max(0, 1) = 1，输出1，正确。第二个for循环因为n - 1 = 0，不会进去。整个流程没有越界，不会出问题。

4.3 字符串末尾和开头的空格陷阱

有一种情况很容易被忽略：输入字符串的首尾就是空格。比如输入abba（前后各两个空格），那么最长的对称子串其实是abba这整个长度为6的串？等等，让我验证一下：前两个空格和后两个空格对称，中间abba对称，所以整个" abba "确实是回文串，长度为6。

但如果你在处理输入时用了类似cin >> s然后自己拼接的做法，或者在判断回文前做了去除首尾空格的"预处理"，那答案就会变成4（只剩abba）。这道题的题面并没有说要去掉首尾空格，字符串是什么就是什么，不要自作主张地清洗数据。我在给别人review代码时就遇到过这个错误，那个人觉得自己很聪明加了trim操作，结果白白丢了一个测试点的分。

5. 从中心扩展到Manacher：什么时候才需要更快的算法

写完中心扩展法之后，我忍不住想一个问题：这道题用O(n^2)过了，但有没有什么场景必须用O(n)的Manacher算法？

Manacher算法的核心思想是利用已经计算过的回文半径来避免重复扩展。它维护一个当前已知的最右覆盖范围，以及对应的回文中心。在计算新位置的回文半径时，先看这个位置是否在已知覆盖范围内，如果是，就利用对称点的回文半径做一个初始估值，再从这个估值继续往外扩。这样每个字符最多被扩展几次，总体复杂度降到O(n)。

我在LeetCode上见过最长回文子串的题目，字符串长度可以到1000，O(n^2)也能过。但有些面试场景或者竞赛场景会把字符串长度拉到10^5甚至更大，这时候中心扩展法就撑不住了，必须得上Manacher。如果你只是备考天梯赛，中心扩展法足够；但如果你想把字符串算法的基础打牢，Manacher还是值得花时间搞懂的。

我给自己留了一个Manacher的模板，贴在这里做个备份：

string preProcess(string s) { int n = s.size(); string t = "#"; for (char c : s) { t += c; t += '#'; } return t; } int manacher(string s) { if (s.empty()) return 0; string t = preProcess(s); int m = t.size(); vector<int> p(m, 0); int center = 0, right = 0; int maxLen = 0; for (int i = 0; i < m; i++) { int mirror = 2 * center - i; if (i < right) p[i] = min(right - i, p[mirror]); while (i - p[i] - 1 >= 0 && i + p[i] + 1 < m && t[i - p[i] - 1] == t[i + p[i] + 1]) { p[i]++; } if (i + p[i] > right) { center = i; right = i + p[i]; } maxLen = max(maxLen, p[i]); } return maxLen; }

它先把原字符串的每个字符用#间隔开，这样奇偶长度就能统一处理。p[i]表示以i为中心的回文半径。最后返回的maxLen就是原始字符串的最长回文长度。这个方法我实测下来非常稳，但理解起来确实比中心扩展法费劲。如果你连中心扩展法的思路还没吃透，不建议一上来就啃Manacher，容易把人绕晕。

6. 复盘：我在实测中踩过的坑和最终体会

最后聊聊这次重做L2-008时踩的几个坑，算是给后来人提个醒。

第一个坑是输入。我第一次写的时候顺手就用了cin >> s，本地测试输入"abcba"没问题，一提交错得莫名其妙。后来仔细一看测试样例，里面赫然有空格和标点，瞬间明白了。吃一堑长一智，之后凡是字符串题目，我都会在动手前先想清楚——字符串中间到底能不能有空格？如果可能，一律getline，不给自己留隐患。

第二个坑是初始化。我一开始把ans初始化为1，心想哪个字符串没有长度1的回文？结果如果输入是空行，ans就应该为0，直接输出1就错了。虽然PTA可能不会给空串做测试点，但严谨起见，初始化为0是最稳定的选择。

第三个坑是调试心态。中心扩展法这种代码如果输出不对，最高效的排查方式不是盯着屏幕看，而是自己手写一个短字符串，一步一步把left、right、ans的变化过程画出来。比如输入"abcb"，画一遍就会发现，奇数中心在'c'的时候，扩展"bcb"长度为3，答案更新成3；偶数中心在'c'和'b'之间不匹配，不会误更新。整个过程一目了然，比在脑子里空想要快得多。

回到这道题本身。L2-008作为天梯赛L2级别的题目，难度设置得很合理。它不要求你掌握多冷门的算法，中心扩展法就是标准答案，但它偏偏在输入处理和边界条件上给你埋了雷，考察的就是你有没有认真读题、有没有扎实的编码习惯。这比单纯考一个难懂的数据结构有意义。

如果你正在备考天梯赛，我建议把这道题当作一道"入门级回文串综合题"来做。先用暴力方法跑通思路，再用中心扩展法优化，最后有余力再看Manacher。三步走完，你对回文串这一族问题的理解就算初步打通了。下次再遇到"回文子串数量""回文串分割"这类变种题，你心里至少有个底，知道从哪个方向入手。