manacher algorithm

#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <string>#include <algorithm>#include <math.h>#define ll long long#define Fast_io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);#define file freopen(\"input.in\", \"r\", stdin);using namespace std;const int N = 2e7 + 10;int main(){Fast_io;string str;while (cin >> str){string s;s += \"@#\";//中心拓展算法int i;for (i = 0; i < str.size(); i++){s += str[i];s += \'#\';}s += \'%\';int p[110000 * 2 + 5] = {0};int mid = 0, R = 0, maxn = 0;//R存的值是匹配到的回文串的下一位失配的；for (i = 1; i < s.size()- 1; i++){p[i] = i < R ? min(R - i, p[mid * 2 - i]) : 1;//因为R是储存的已匹配最大值得下一位，//所以，R- i就是已匹配的最大位数， p[mid * 2 - i] 是它的回文串左半边的最大个数，// 1是只有它自己, 前面没有一个回文串包含它，重新中心拓展,//改成0也行，但是多匹配了自己一位， 没啥用。while (s[i - p[i]] == s[i + p[i]])p[i]++;if (i + p[i] > R){R = i + p[i];mid = i;}maxn = max(maxn, p[i]);}//maxn 就是p[i],      下面这个公式左边我把本身算了进去，右边没有算//maxn的值可以自己算算，(左边: maxn / 2 )+ (右边: maxn / 2 - 1 );cout << maxn - 1 << endl;}return 0;}