代码

// This code is AI-generated. (AI 生成的代码)
#pragma GCC optimize("O3")
#include <sys/auxv.h>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <cstring>

static const char D2TAB[201] =
"00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899";

struct DuckInfo {
    unsigned long abi; const char *in; unsigned long in_size;
    char *out; unsigned long out_limit, out_size;
    char *err; unsigned long err_limit, err_size;
    const char *IB; unsigned long IB_limit; char *OB; unsigned long OB_limit; unsigned long tsc;
} __attribute__((packed));
static struct DuckInfo *g_d;
struct IO_Tp
{
	const static int _O_Buffer_Size = 2 << 20;
	char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;
	
	~IO_Tp() { if (g_d) g_d->out_size = (unsigned long)(_O_pos - g_d->out); else fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }
	
	IO_Tp &operator<<(int n)
	{
		char _buf[12];
		char *_p = _buf;
		while (n >= 100)
		{
			int r = n % 100;
			n /= 100;
			*_p++ = D2TAB[r * 2 + 1];
			*_p++ = D2TAB[r * 2];
		}
		if (n >= 10)
		{
			*_p++ = (char)('0' + n % 10);
			*_p++ = (char)('0' + n / 10);
		}
		else
			*_p++ = (char)('0' + n);
		while (_p != _buf)
			*_O_pos++ = *--_p;
		return *this;
	}
	
	IO_Tp &operator<<(char ch)
	{
		*_O_pos++ = ch;
		return *this;
	}
} IO;

const int Max_N = 100005;

namespace SA_IS
{
	int *sa;
	
	template<typename _Char>
	void sais_core(const int n, const int m, const _Char s[], char type[], int lms[], int cnt[])
	{
		int n1 = -1;
		
		type[n] = 1;
		for (int i = n - 1; i >= 0; --i)
		{
			type[i] = s[i] == s[i + 1] ? type[i + 1] : s[i] < s[i + 1];
			if (type[i] == 0 && type[i + 1] == 1)
				type[i + 1] = 2, lms[++n1] = i + 1;
		}
		for (int a = 0, b = n1; a < b; ++a, --b) { int t = lms[a]; lms[a] = lms[b]; lms[b] = t; }
		
		memset(cnt, 0, (size_t)m * sizeof(int));
		for (int i = 0; i <= n; ++i)
			++cnt[static_cast<int>(s[i])];
		for (int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
		
		auto induced_sort = [&](const int v[])
		{
			memset(sa, 0, (size_t)(n + 1) * sizeof(int));
			
			int *cur = cnt + m;
			auto push_S = [&](const int x) { sa[--cur[static_cast<int>(s[x])]] = x; };
			auto push_L = [&](const int x) { sa[cur[static_cast<int>(s[x])]++] = x; };
			
			memcpy(cur, cnt, (size_t)m * sizeof(int));
			for (int i = n1; i >= 0; --i)
				push_S(v[i]);
			
			memcpy(cur + 1, cnt, (size_t)(m - 1) * sizeof(int));
			for (int i = 0; i <= n; ++i)
				if (sa[i] > 0 && type[sa[i] - 1] == 0)
					push_L(sa[i] - 1);
			
			memcpy(cur, cnt, (size_t)m * sizeof(int));
			for (int i = n; i >= 0; --i)
				if (sa[i] > 0 && type[sa[i] - 1])
					push_S(sa[i] - 1);
		};
		
		induced_sort(lms);
		
		auto lms_equal = [&](int x, int y)
		{
			if (s[x] == s[y])
				while (s[++x] == s[++y])
					if (type[x] == 2)
						return true;
			return false;
		};
		
		int ch = -1;
		
		int *s1 = sa;
		for (int i = 0; i < n; ++i) { int x = sa[i]; if (type[x] == 2) *s1++ = x; }
		for (int i = 0; i <= n1; ++i)
			s1[sa[i] >> 1] = ch += ch <= 0 || !lms_equal(sa[i], sa[i - 1]);
		for (int i = 0; i <= n1; ++i)
			s1[i] = s1[lms[i] >> 1];
		
		if (ch < n1)
			sais_core(n1, ch + 1, s1, type + n + 1, lms + n1 + 1, cnt + m);
		else
			for (int i = 0; i <= n1; ++i)
				sa[s1[i]] = i;
		
		auto tmp = lms + n1 + 1;
		for (int i = 0; i <= n1; ++i)
			tmp[i] = lms[sa[i]];
		induced_sort(tmp);
	}
	
	template<typename _Char>
	void main(const _Char s[], const int n, const int m)
	{
		static int _lms[Max_N], _cnt[Max_N << 1];
		static char _type[Max_N << 1];
		
		/*
		for (int i = 0; i != n; ++i)
			assert(1 <= s[i] && s[i] < m);
		assert(s[n] == 0);
		*/
		
		sais_core(n, m, s, _type, _lms, _cnt);
	}
}

template<typename _Char>
void klaap(const _Char s[], const int sa[], int lcp[], const int n)
{
	static int rk[Max_N];
	for (int i = 0; i < n; ++i)
		rk[sa[i]] = i;
	for (int i = 0, h = lcp[0] = 0; i < n; ++i)
		if (h -= h != 0, rk[i])
		{
			for (int j = sa[rk[i] - 1]; i + h < n && j + h < n && s[i + h] == s[j + h]; ++h)
				;
			lcp[rk[i]] = h;
		}
}

int main(int argc, char **argv)
{
	static char s[Max_N];
	static int sa[Max_N], lcp[Max_N];
	
	g_d = (struct DuckInfo *)getauxval(0x6b637564UL);
	{
		const char *q = g_d->in;
		while (*q && (unsigned char)*q <= 32u) q++;
		char *cp = s;
		while ((unsigned char)*q > 32u) *cp++ = *q++;
		*cp = 0;
	}
	IO._O_pos = g_d->out;
	int N = strlen(s);
	
	SA_IS::sa = sa;
	SA_IS::main(s, N, 128);
	klaap(s, sa + 1, lcp, N);
	
	for (int i = 1; i <= N; ++i)
		IO << sa[i] + 1 << " \n"[i == N];
	for (int i = 1; i < N; ++i)
		IO << lcp[i] << " \n"[i == N];
	if (N == 1)
		IO << '\n';
	
	return 0;
}

评测结果