题解 | #最长回文子串# Manacher解法

class Solution {
  public:
    int init(const char* s) {
        int len = strlen(s);
        for (int i = 0; i < (len << 1); i += 2) {
            tmp[i] = '#';
            tmp[i + 1] = q[i >> 1];
        }
        tmp[2 * len] = '#';
        tmp[2 * len + 1] = 0;
        return 2 * len + 1;
    }

    int manacher(const char* s, int len) {
        int c = 0, r = 0, ans = 0;
        for (int i = 0; i < len; i++) {
            if (i < r) {
                p[i] = min(r - i, p[2 * c -i]);
            } else {
                p[i] = 1;
            }
            while (i - p[i] >= 0 && i + p[i] < len && s[i - p[i]] == s[i + p[i]]) 
                p[i]++;
            if (p[i] + c > r) {
                c = i;
                r = p[i] + c;
                ans = max(ans, p[i]);
            }
        }
        return ans - 1;
    }

    int getLongestPalindrome(string A) {
        for(int i = 0; i < A.size(); i++){
            q[i] = A[i];
        }
        q[A.size()] = 0;
        int len = init(q);
        return manacher(tmp,len);
    }

    const unsigned int N = 300010;
    char q[300010]; // 输入的字符串
    char tmp[300010 << 1];
    int cnt[300010] ;
    int p[300010 << 1];
};

#include<iostream>
#include<cstring>
#include<iterator>
using namespace std;

/*

马拉车算法
1、将字符串统一成奇数：给字符串添加间隔特殊字符
2、创建P数组，记录最大回文长度
3、循环字符串寻找最大长度

*/
const unsigned int N = 300010;
char q[N]; // 输入的字符串
char tmp[N << 1];
int cnt[N] ;
int p[N << 1];

/*
将字符串每个字符中间(包括两边)插入一个字符串中不存在的任意字符，并返回最终的长度字符串
*/
int init(const char* s) {
	int len = strlen(s);
	for (int i = 0; i < (len << 1); i += 2) {
		tmp[i] = '#';
		tmp[i + 1] = q[i >> 1];
	}
	tmp[2 * len] = '#';
	tmp[2 * len + 1] = 0;
	return 2 * len + 1;
}

int manacher(const char* s, int len) {
	// 最大回文字符串中心角标， 最大回文字符串右侧角标 ，最大回文字符串值
	int c = 0, r = 0, ans = 0;
	//	遍历字符串获取回文值
	for (int i = 0; i < len; i++) {
		// 如果i在c到r的范围内，则直接使用前面的结果
		if (i < r) {
			p[i] = min(r - i, p[2 * c - i]); // 左边（j） 为中心的回文是有可能比r - i 要小的，所以此处需要取最小值 
		}
		else {
			p[i] = 1;
		}
		// 从指定的中心往两边扩展
		while (i - p[i] >= 0 && i + p[i] < len && s[i - p[i]] == s[i + p[i]]) p[i]++;
		//更新c和r 
		if (p[i] + c > r) {
			c = i;
			r = p[i] + c;
			ans = max(ans, p[i]);
		}
	}
	return ans - 1;
}

int main() {
//	while (cin >> q) {
//		int len = init(q);
//		cout << manacher(tmp, len) << endl;
//	}
	cin >> q;
	int len = init(q);
	cout << manacher(tmp, len) << endl;


	return 0;
}