USACO 07DEC Best Cow Line G

讲一讲自己的错解思路：因为考虑到每次查找会超时，所以我在查找一次的时候将第一个不同的但更小的下标记录下来，然后相等时优先选离其最近的边界。

下见代码\(qwq\)。

#include <cstdio>
#include <cstdlib>
#include <cstring>

char s[500002], ans[500002];
int n, flag, cnt;

int read() {
	int x = 0, f = 1; char S;
	while((S = getchar()) > '9' || S < '0') {
		if(S == '-') f = -1;
		if(S == EOF) exit(0);
	}
	while(S <= '9' && S >= '0') {
		x = (x << 1) + (x << 3) + (S ^ 48);
		S = getchar();
	}
	return x * f;
}

void Find(const int l, const int r) {
    int dis = 0;
    while(l + dis < r - dis && s[l + dis] == s[r - dis]) ++ dis;
    if(l + dis == r - dis) flag = (s[l + dis] > s[l + dis - 1] ? l + dis - 1 : l + dis);
    else if(l + dis > r - dis) flag = l + dis - 1;
    else flag = (s[l + dis] > s[r - dis] ? r - dis : l + dis);
}

int main() {
    int l, r;
    n = read();
    for(int i = 0; i < n; ++ i) {
        s[i] = getchar();
        getchar();
    }
    l = 0; r = n - 1;
    flag = -1;
    while(l != r) {
        if(s[l] < s[r]) ans[++ cnt] = s[l], ++ l;
        else if(s[l] > s[r]) ans[++ cnt] = s[r], -- r;
        else {
            if(flag < l || flag > r) flag = -1;
            if(flag == -1) Find(l, r);
            if(flag - l < r - flag) ans[++ cnt] = s[l], ++ l;
            else ans[++ cnt] = s[r], -- r;
        }
    }
    ans[++ cnt] = s[l];
    for(int i = 1; i <= cnt; ++ i) {
        putchar(ans[i]);
        if(i % 80 == 0) putchar('\n');
    }
    return 0;
}

这份代码有\(60pts\)。

我们来举个例子：

11
B
B
A
A
B
C
B
A
A
B
B

这组数据我的程序会先输出\(BBAA\)，再输出\(BBB\)，而这显然没有\(BBA\)优。()

好的我们讲讲正解：\(SA\)。

其实就是判断字符串的大小。我们将原串反转一下再接上去，就可以分别表示前缀与后缀了。（PS：中间的符号可以不加）

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 5e5 + 2;

int ans[N], cnt, n, m, SA[N << 1], rk[N << 1], h[N << 1], tax[N << 1], tp[N << 1], a[N << 1];

int read() {
	int x = 0, f = 1; char S;
	while((S = getchar()) > '9' || S < '0') {
		if(S == '-') f = -1;
		if(S == EOF) exit(0);
	}
	while(S <= '9' && S >= '0') {
		x = (x << 1) + (x << 3) + (S ^ 48);
		S = getchar();
	}
	return x * f;
}

void Sort() {
	for(int i = 0; i <= m; ++ i) tax[i] = 0;
	for(int i = 1; i <= n; ++ i) ++ tax[rk[tp[i]]];
	for(int i = 1; i <= m; ++ i) tax[i] += tax[i - 1];
	for(int i = n; i >= 1; -- i) SA[tax[rk[tp[i]]] --] = tp[i];
}

int cmp(const int x, const int y, const int d) {return tp[x] == tp[y] && tp[x + d] == tp[y + d];}

void Suffix() {
	for(int i = 1; i <= n; ++ i) rk[i] = a[i], tp[i] = i;
	m = 122; Sort();
	for(int w = 1, p = 1, i; p < n; w <<= 1, m = p) {
        for(p = 0, i = n - w + 1; i <= n; ++ i) tp[++ p] = i;
        for(i = 1; i <= n; ++ i) if(SA[i] > w) tp[++ p] = SA[i] - w;
        Sort(); swap(rk, tp); rk[SA[1]] = p = 1;
        for(int i = 2; i <= n; ++ i) rk[SA[i]] = cmp(SA[i], SA[i - 1], w) ? p : ++ p;
	}
	int k = 0, j;
    for(int i = 1; i <= n; h[rk[i ++]] = k)
        for(k = k ? k - 1 : k, j = SA[rk[i] - 1]; a[i + k] == a[j + k]; ++ k);
}

int main() {
	char ch;
	int l = 1, r;
	n = read();
	r = n;
	for(int i = 1; i <= n; ++ i) {
		ch = getchar(); getchar();
		a[i] = ch;
	}
	a[n + 1] = '$';
	for(int i = n + 2; i <= (n << 1) + 1; ++ i) a[i] = a[2 * n + 2 - i];
	n = (n << 1) + 1;
	Suffix();
	n = (n - 1 >> 1);
	while(l <= r) {
        if(a[l] < a[r]) ans[++ cnt] = a[l ++];
        else if(a[l] > a[r]) ans[++ cnt] = a[r --];
        else {
            if(rk[l] > rk[2 * (n + 1) - r]) ans[++ cnt] = a[r --];
            else ans[++ cnt] = a[l ++];
        }
	}
	for(int i = 1; i <= cnt; ++ i) {
        printf("%c", ans[i]);
        if(i % 80 == 0) putchar('\n');
	}
	return 0;
}