萌新正在写Manacher

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

string s, rs = "&#";
ll ans = 1;
int R, C;
int dp[22000005];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> s;
	for (int i = 0;i < s.size(); ++i)
		rs += s[i], rs += '#';
	dp[0] = 1, R = 0, C = 0;
	for (int i = 1;i < rs.size(); ++i)
	{
		if (C == -1 || i >= R)
			dp[i] = 1;
		else if (2 * C - i - dp[2 * C - i]/*这是i的对称点的回文串的左端点*/ >= C - dp[C])
			dp[i] = dp[2 * C - i];
		else
			dp[i] = C + dp[C] - i;
		for (int j = i + dp[i], k = i - dp[i];j < rs.size() && k >= 0 && rs[j] == rs[k]; ++j, --k)
			++dp[i];
		if (i + dp[i] > R)
			R = i + dp[i], C = i;
		ans = max((ll)dp[i], ans);
	}
	cout << ans - 1;
	return 0;
}

萌新照着算法竞赛下册第九章第二节第二小节的思路，自己写了一份代码，A了。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

char c[11000005], rc[22000005];
int ans = 1;
int R, C, lc, lrc;
int dp[22000005];
int main(){
	scanf("%s", c);
	rc[0] = '&', rc[1] = '#', lc = strlen(c), lrc = 2;
	for (int i = 0;i < lc; ++i)
		rc[lrc++] = c[i], rc[lrc++] = '#';
	dp[0] = 1, R = 0, C = 0;
	for (int i = 1;i < lrc; ++i)
	{
		if (i < R)
			dp[i] = min(dp[(C << 1) - i], dp[C + dp[C] - i]);
		else
			dp[i] = 1;
		while (rc[i + dp[i]] == rc[i - dp[i]]) ++dp[i];
		if (i + dp[i] > R)
			R = i + dp[i], C = i;
		ans = max(dp[i], ans);
	}
	printf("%d", ans - 1);
	return 0;
}
//因为一些神奇的原因T在了9和16
//假如在18行~20行之间判断对称点的回文串是否越过dp[C]-C则不会T
//太神奇了 

萌新决定跟着书上的标程打一遍。但是TLE on #9 #15

萌新感到十分神奇，于是发了一个帖子。这到底是怎么回事呢