rt,题目是P3805

题目传送门

#include <bits/stdc++.h>
using namespace std;
const int N = 2.2e7 + 5; //1.1e7*2
int p[N];

int main() {
	freopen("1.in", "r", stdin);
	freopen("1.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	string s, ss = "#";
	cin >> s;
	int l = s.size(), ans = 0;
	for (int i = 0; i < l; i++)
		ss = ss + s[i] + "#";
	//cout << ss << endl;
	int c = 0, r = 0;
	l = (l << 1 | 1);
	for (int i = 0; i < l; i++) {
		if (i < r)
			p[i] = min(p[2 * c - i], r - i);
		else
			p[i] = 1;
		while ((i + p[i] < (l << 1 | 1) ) && (i - p[i] >= 0) && (ss[i + p[i]] == ss[i - p[i]]) )
			p[i]++;
		if (i + p[i] > r)
			r = i + p[i], c = i;
		ans = max(ans, p[i]);
	}
	cout << ans - 1 << "\n";
	return 0;
}