题解 | #最长回文子串#

马拉车算法 Manacher's Algorithm 复杂度O(n)

#include<stdio.h>
#include<stdlib.h>
char* insert(char* str, int n) {
	char* res = (char*)malloc(sizeof(char) * (2 * n + 1));
	int i = 0;
	while (str[i]) {
		res[2 * i] = '#';
		res[2 * i + 1] = str[i];
		i++;
	}
	res[2 * i] = '#';
	return res;
}
int manacher(char* str, int n) {
	int max = 0, cen = 0, r = 0,len=0;
	int* mnc = (int*)malloc(sizeof(int) * n);
	mnc[0] = 0;
	for (int i = 0; i < n; i++) {
		int i1 = 2 * cen - i;
		if (i <= r && i+mnc[i1]<r) {
			mnc[i] = mnc[i1];
		}
		else {
			if (i > r)
				len = 0;
			else
				len = r - i;
			while (i + len + 1 < n && i - len - 1 >= 0 && str[i + len + 1] == str[i - len - 1])
				len++;
			mnc[i] = len;
			if (i + len > r) {
				cen = i;
				r = i + len;
			}
		}
		max = max > mnc[i] ? max : mnc[i];
		//printf("cen=%d\tr=%d\tmnc[%d]=%d\tmax=%d\n\n", cen, r, i, mnc[i], max);
	}
	return max;
}
int main() {
	char str[351];
	while (~scanf("%s", str)) {
		int i = 0;
		while (str[i])i++;
		if (i & 1)
			printf("%d\n", manacher(str, i) * 2 + 1);
		else {
			printf("%d\n", manacher(insert(str, i), 2 * i + 1));
		}
	}
}