小学一下。
首先是用一个在回文串题目中的的技巧，用来减少分讨，如果想到这个的话说不定thusc2024 d1t1就切了。具体来说，就是在每个字符之间都插入一个#，然后在开头和结尾插入随便两个不同的字符。然后就只有回文中心在字符上的情况了。
首先设\(p_{i}\)为当前位置为中心的最大回文半径。mr为当前做到的回文串的右端点，mid为当前做到的回文串的中心。
首先i肯定大于mid，因为根据代码，mid由i更新，而i是一直在前进的
分两类讨论:
mid<i<mr
p[i]=min(p[mid*2-i],mr-i+1);
分两部分解释。设j为i关于mid的对称点,ml为mr关于mid的对称点。如果i+p[j]>mr，那么我们不能保证[i-p[j],i+p[j]]是回文串,所以为mr-i+1。否则根据对称性，p[i]就等于p[j]
i>=mr
直接暴力向两边拓展即可。
时间复杂度证明
如果当前p[i]==p[j]那么说明不能向两边拓展了，就不会进到while里去。如果当前p[i]=mr-i+1，那么就可能向两边拓展，同时更新mr。向两边拓展也更新了mr，所以每次的while循环都对应着mr的拓展，每次mr的拓展都对应着while循环，因为mr最多为len,那么最多进len次while，所以时间复杂度线性
标签：manacher,两边,mid,笔记,学习,while,拓展,mr,回文 From： https://www.cnblogs.com/wuhupai/p/18202691