代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef unsigned long long u64;
const int maxn = 1E6 + 10;
const u64 base = 20123;

int n;
char s[maxn];
u64 f[maxn], p[maxn];

void init() {
	for (int i = p[0] = 1; i <= n; i++)
		f[i] = f[i - 1] * base + s[i],
		p[i] = p[i - 1] * base;
}
u64 get_hash(int l, int r) {
	return f[r] - f[l - 1] * p[r - l + 1];
}
int lcp(int x, int y) {
	int l = 1, r = n - max(x, y) + 1, ans = 0;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (get_hash(x, x + mid - 1) == get_hash(y, y + mid - 1))
			ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	return ans;
}

int a[maxn];
bool cmp(int x, int y) {
	int ans = lcp(x, y);
	return s[x + ans] < s[y + ans];
}

int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1); init();
	for (int i = 1; i <= n; i++)
		a[i] = i;
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; i++)
		printf("%d ", a[i]);
	printf("\n");
	for (int i = 1; i < n; i++)
		printf("%d ", lcp(a[i], a[i + 1]));
	return 0;
}

评测结果