字符串

Manacher

r表示当前最大回文串的右边界+1，c记录该回文串的中心位置

主要利用了回文串的对称性

int malache(string s) {
	int len = s.length(), l = 0;
	t[l] = '$';t[++l] = '#';
	for (char c : s)
		t[++l] = c, t[++l] = '#';
	int r = 0, c = 0;
	for (int i = 1;i <= l;++i) {
		p[i] = i < r ? min(p[2 * c - i], r - i) : 1;
		while (t[i + p[i]] == t[i - p[i]]) ++p[i];
		if (i + p[i] > r) r = i + p[i], c = i;
	}
	return l;
}