马拉车算法其实就是解决一个字符串中由某个位置为中心的最大回文串长度：（下图中蓝色部分为字符串，绿色框中的值就是以这个位置为中心的最大回文串长度）
其次，我们发现最底下的一排绿色数字涉及到空隙，所以我们可以把字符串扩展一下：
比如，原字符串是 $\texttt{abccabbc}$，那么扩展之后就是：
（LaTeX炸了） $\texttt{\color{RoyalBlue}@\color{default}#\color{default}a\color{RoyalBlue}#\color{default}b\color{RoyalBlue}#\color{default}c\color{RoyalBlue}#\color{default}c\color{RoyalBlue}#\color{default}a\color{RoyalBlue}#\color{default}b\color{RoyalBlue}#\color{default}b\color{RoyalBlue}#\color{default}c\color{RoyalBlue}#\color{RoyalBlue}&}$
第一个和最后一个字符可以自己定，但是最好不要和原字符串中的字符、中间插入的字符冲突（相等）。
注：其实还有第二种扩展方法：
$\texttt{\color{RoyalBlue}#\color{default}a\color{RoyalBlue}#\color{default}b\color{RoyalBlue}#\color{default}c\color{RoyalBlue}#\color{default}c\color{RoyalBlue}#\color{default}a\color{RoyalBlue}#\color{default}b\color{RoyalBlue}#\color{default}b\color{RoyalBlue}#\color{default}c\color{RoyalBlue}#\color{default}}$
还是，中间字符不能与原串字符相等。
下面统一设「以下标 $i$ 为中心的最大回文串长度除以 $2$ 并下取整」后的答案为 $p_i$。
然后，我们就开始求 $p$ 数组了，当我们求到 $p_i$ 的时候，我们看前面求出的 $p_j+j$ 的最大值是多少（设为 $r$），即 $\max\limits_{j=1}^{i-1} { p_j+j }$，同时求出最大的 $p_j+j$ 对应的 $j$（设为 $c$）。
并且，我们求出 $i$ 的对称点 $i’$，对称中心为 $c$，显然 $i’=2c-i$。
然后，分类讨论：
注：图中 $r$ 的意思与上面说的 $r$ 的意思有冲突，统一以上面说的定义为准。
- $i>r$，那么暴力算 $p_i$。
- $r-i \geq p_{i’}$，那么 $p_i=p_{i’}$。
- $r-i<p_{i’}$，那么让 $p_i=r-i$，继续暴力扩展。
最后就是时间复杂度问题了。
关于时间复杂度的证明，我们可以分类讨论 $p_i$ 是用那种情况求值的：
- 用情况1转移：$r$ 肯定会增加。
- 用情况2转移：复杂度忽略。
- 用情况3转移：$r$ 也肯定会增加。
由于每时每刻，$r$ 都小于等于 $n$，所以总复杂度就是 $O(n)$ 的。
这里解释一个代码细节，我的模板中，可以发现 $p_i$ 赋的初始值是 $\min(r-i,p_{i’})$，有人会问，如果最小值最后取的是 $p_{i’}$，会不会多复杂度（继续扩展）？答案是否定的，因为 $p_{i’}$ 是极大值，如果能继续扩展，那么 $p_{i’}$ 也会增大，证毕。