勤劳的tc又来了这回是马拉车。讲道理我应该先学kmp的。算了kmp之后在学。马拉车算法是求最大回文串的。受用面很窄。
ok接下来就是algorithm time
第一步是先将原本的字符串初始化。将每个字符用一个符号包裹，一般是#。
在这个时候字符串无论如何就都是偶数了。有什么用呢，举个例子。我们从下标为1开始。
#1#2#2#1#
看这里中心位置是一个#号然后他的下标是index=5，然后这个字符串的半径是r=5，然后原字符串就是 1221，可以看出这回字符串是从0（index-r）开始后四位（r-1）。这里是他最神奇的地方。也让他简便了很多。
我们一般字符串都是从下标0开始的所以我们在他前面加一个字符串里没有的字符一般,我取的是$。
当然这个算法不只这么一点。首先他有一个数组p[i],记录他每个位置的回文串的大小，然后又一个变量mx记录回文串可以到达的最右边下标，他还有个变量id记录该字符串的下标。

这里在开始匹配前记录回文串半径最小值。  
当```mx>i```
很容易我们可以得到``` k=id*2-i```是i 关于id的对称点。而以id为中心
mx-id为半径的字符串是对称的，所以当p[k]的边界在id的边界之内，以下标为i的字符串的半径为p[k]的字符串一定是回文串。而当p[k] 大于id的边界的时候就不能保证对称性了，所以这里就取mx-i。  
当mx < i 这里我们就不能确定对称性了，所以直接取1.
以下是代码:

include

using namespace std;
string name,lo;
string lon(){
lo=”$”;
int i=0;
while(name.size()>i){
lo+=”#”;
lo+=name[i];
i++;
}
lo+=”#”;
int si=0,index=0;
vector p(lo.size(),0);
i=0;
int mx=0;
int id=0;
int len=lo.size();
for(i;ii? min(p[id*2-i],mx-i):1;
while(lo[i-p[i]]==lo[i+p[i]]) p[i]++;
if(mxsi){
index=i;
si=p[i];
}
}
cout<<name<<” “<<endl;
return name.substr((index-si)/2,si-1);
}

int main(){
name=”11123123312123311”;
cout<<lon();
return 0;
}
```