Aimee

马拉车算法，以优秀复杂度求解回文子串

我认为的关键：减少重复计算

用r表示当前已知回文子串右边界，id表示其中心的位置

显然我们当下求解的i应该再id右边

如果这个i在r的左边，那么显然在id的中心中，因该有一个关于i的对称点，并且因为位置的的原因，左边点的回文是已经被算出来了的，那样可以直接解决i到r部分的回文

然而更远的部分呢？就需要暴力扩展

#include
#include
#include
#include
using namespace std;
string s,ss;
int id;
int r;
int p[110000001];
int Aimee;
int main(){
    cin>>s;
    int l=s.length();   
    for(int i=0;i=0&&i+p[i]r){
            r=p[i]+i-1;
            id=i;
        }
        Aimee=max(Aimee,p[i]);
    }
    cout<