马拉车算法
[TOC]
简介
马拉车算法是一种在O(n)时间内求一个字符串的最长回文子串的算法
思路
对于最长回文子串,我们可以有很多朴素算法
- 比如穷举所有子串,然后验证这些子串是否是回文的,这样的复杂度是O(n^3),
- 比如我们遍历数组,对于每一个元素,我们都认为其是某个回文子串的中心,我们同时向两边伸展,然后取其中的最大值,这样的算法的复杂度是O(n^2)
马拉车算法就是在方法2的基础上进行了扩展,注意方法2做了大量重复的计算,比如,整个数组就是一个回文串,其包含两个对称的小的回文串,这样就做了很多无用功.马拉车算法就是充分利用了这种性质来减少时间复杂度的.
变量
我们设置以下变量
```mx```是目前已知的最长回文子串的最右一位**的后一位**
```Len[]```: **Len[i]表示以i为中心的最长子串能扩展的最长位置-i+1**,即i+Len[i]得到的位置是以i为中心的最长回文子串扩展的最远位置的下一位(此处的设计是为了呼应上文的mx) // Len[]数组的大小应该为原字符串的大小的2倍还多,且Len[0]一定为0
### 预处理
另外我们还要对字符串进行预处理
因为我们发现回文有两种情况,一种是奇数的,一种是偶数的,偶数的形式是没有中心位置的,这就对后续的计算带来极大的不方便,因此我们进行预处理.
预处理的思路是让所有的回文串都变成奇数形式.我们采用如下的思路
```原字符串: ababc```
```预处理后:$#a#b#a#b#c#```
**注意文中的$和#应该都为在字符串本体中不会出现的字符**
这样处理过后,除去开头的$之外,字符串主体一定是奇数
### 算法
我们逐步讨论一下这种情况
对于给定的```i```我们找一个和它关于```id```对称的```j```,也就是 ```id-j == i-id```,换言之就是```j==2*id-i```如果发生这种情况,我们就不难发现,```i```和```j``` 的最长回文子串**在id的回文串范围内的部分应该是一模一样的**,但是在外面的部分就无法保证了,当然,最好的情况是```i```和```j```的回文子串范围都很小,这样就保证了**他俩的回文子串一定一模一样**,对于超出的部分我们也没有办法,只能手动扩展,也就是上文的方法2.
如果i大于mx,说明我们无法用已知的最长回文子串来优化这个计算,所以只能老老实实用上文的方法2来计算
经过以上的处理我们不要忘记更新``id``和```mx```,同时记录最长的回文子串的长度```maxn```(代码中写的是sum),最后输出答案即可.
但是! 我们之前进行了预处理,而且Len[i]仅仅是一半的数组长度,这个该怎么进行转换才能得到最长回文子串的答案呢?
其实如果不考虑预处理的话,仅仅就预处理后的字符串而言,回文子串长度是 ```1+2*(Len[i]-1)```,也就是 ```2*Len[i]-1```,预处理后的字符串长度(不考虑开头的$),是```2*s.size()+1``` ,也就是说两个式子联立,就得到了```2*Len[i]-1 == 2*s.size()+1```解得 ```s.size()==Len[i]-1```
所以最后的答案是```max(Len[i]-1)```
## 代码
```c
// hihocoder 1032
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
string s;
string ss;
int lss;
int Len[2000100]; // 一定是要原字符串的二倍多,开小了会RE
int mx;
int id;
void work() { // 马拉车算法模板(无任何更改)
Len[0] = 0;
lss = ss.size();
int sum = 0;
for (int i = 1; i < lss; ++i) { // 自1开始,不用理会开头的$
if (i < mx) {
Len[i] = min(mx - i, Len[2 * id - i]);
} else {
Len[i] = 1;
}
while (ss[i - Len[i]] == ss[i + Len[i]]) {
++Len[i];
}
if (i + Len[i] > mx) {
mx = i + Len[i];
id = i;
sum = max(sum, Len[i]);
}
}
cout << sum - 1 << endl;
}
int main() {
int T;
cin >> T;
while (T--) {
mx = 0;
id = 0;
cin >> s;
int len = s.size();
ss = "$#";
for (int i = 0; i < len; ++i) {
ss += s[i];
ss += "#";
}
work();
}
return 0;
}
