请对这个人的题解代码加上注释：P2870 USACO07DEC最佳牛线黄金Best Cow Line Gold题意给一个字符串每次只能从两边取加入到答案要求取出来之后答案的字典序最小。���len=500000500000思路因为这道题要求答案字典序最小所以我们有一个贪心策略：每一次都取两端的较小者一直取完。这一定是没有问题的此时局部最优解就是全局最优解。关键是当两端相同时应该怎么办。当字符串为

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#define N 500010
#define M 98244353
#define base 131
template<typename T> inline void read(T &x) {
	x = 0; char c = getchar(); bool flag = false;
	while (!isdigit(c)) {if (c == '-') flag = true; c = getchar(); }
	while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
	if (flag)	x = -x;
}
using namespace std;
int n;
char s[N];
long long ha1[N], ha2[N], bas[N];
//因为要正着的串和反着的串比较，所以要用两个哈希 
//bas[i]:base^i
char ans[N];
int top;
int lef, rig;//left, right

// 比较两端是否相同
inline int che(int len) {
	long long l = ((ha1[lef + len - 1] - ha1[lef - 1] * bas[len]) % M + M) % M;
	long long r = ((ha2[rig - len + 1] - ha2[rig + 1] * bas[len]) % M + M) % M;
	return l == r;
}

// 二分查找相同长度的子串
inline int halffind() {
	int l = 1, r = (rig - lef + 1) >> 1;
	int mid, res = 1;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (che(mid)) {
			res = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return res;
}

int main() {
	read(n);
	for (register int i = 1; i < n; ++i) {
		s[i] = getchar();
		getchar();
	}
	s[n] = getchar();
	bas[0] = 1;
	for (register int i = 1; i <= n; ++i) {
		ha1[i] = (ha1[i - 1] * base + s[i]) % M;
		bas[i] = bas[i - 1] * base % M;
	}
	for (register int i = n; i; --i) {
		ha2[i] = (ha2[i + 1] * base + s[i]) % M;
	}
	
	lef = 1, rig = n;
	int len;
	for (register int i = 1; i < n; ++i) {
		if (s[lef] < s[rig]) {
			ans[++top] = s[lef++];
		} else if (s[rig] < s[lef]) {
			ans[++top] = s[rig--];
		} else {
			len = halffind();
			ans[++top] = s[lef + len] < s[rig - len] ? s[lef++] : s[rig--];
		}
	}
	ans[n] = s[lef];//最后一个直接扔到答案结尾即可，不用判断 
	for (register int i = 1; i <= n; ++i) {
		putchar(ans[i]);
		if (i % 80 == 0)	putchar('\n');
	}
	return 0;
}

注释如下：

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#define N 500010
#define M 98244353
#define base 131
template<typename T> inline void read(T &x) {
	x = 0; char c = getchar(); bool flag = false;
	while (!isdigit(c)) {if (c == '-') flag = true; c = getchar(); }
	while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
	if (flag)	x = -x;
}
using namespace std;
int n;
char s[N];
long long ha1[N], ha2[N], bas[N];
// 因为要正着的串和反着的串比较，所以要用两个哈希 
// bas[i]: base^i
char ans[N];
int top;
int lef, rig;// left, right

// 比较两端是否相同
inline int che(int len) {
	long long l = ((ha1[lef + len - 1] - ha1[lef - 1] * bas[len]) % M + M) % M;
	long long r = ((ha2[rig - len + 1] - ha2[rig + 1] * bas[len]) % M + M) % M;
	return l == r;
}

// 二分查找相同长度的子串
inline int halffind() {
	int l = 1, r = (rig - lef + 1) >> 1;
	int mid, res = 1;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (che(mid)) {
			res = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return res;
}

int main() {
	read(n);
	for (register int i = 1; i < n; ++i) {
		s[i] = getchar();
		getchar();
	}
	s[n] = getchar();
	bas[0] = 1;
	for (register int i = 1; i <= n; ++i) {
		ha1[i] = (ha1[i - 1] * base + s[i]) % M;
		bas[i] = bas[i - 1] * base % M;
	}
	for (register int i = n; i; --i) {
		ha2[i] = (ha2[i + 1] * base + s[i]) % M;
	}
	
	lef = 1, rig = n;
	int len;
	for (register int i = 1; i < n; ++i) {
		if (s[lef] < s[rig]) {
			ans[++top] = s[lef++];
		} else if (s[rig] < s[lef]) {
			ans[++top] = s[rig--];
		} else {
			len = halffind();
			ans[++top] = s[lef + len] < s[rig - len] ? s[lef++] : s[rig--];
		}
	}
	ans[n] = s[lef]; // 最后一个直接扔到答案结尾即可，不用判断 
	for (register int i = 1; i <= n; ++i) {
		putchar(ans[i]);
		if (i % 80 == 0)	putchar('\n');
	}
	return 0;
}
``