题目：[JSOI2007]字符加密

很常见的做法，破环为链，然后以2n为总长再后缀排序，然后对于SA[i] < n 的，说明第i小后缀的编号是小于n的，也就是说，以i开头的编号是合法的，那么输出s[SA[i]+n-1]即可。

代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

const int N = 2e5 + 5;

using namespace std;

int n, rk[N], sa[N], psa[N], k1[N], k2[N], cnt[N], m, len;

char s[N];

int main()

{

	scanf("%s", s);

	n = strlen(s);

	for(int i = 0; i < n; i++)

	    s[i + n] = s[i];

	len = n << 1;

	m = max(len, 300);

	for(int i = 0; i < len; i++)

	    cnt[(int)s[i]]++;

	for(int i = 1; i < m; i++)

	    cnt[i] += cnt[i - 1];

	for(int i = 0; i < len; i++)

	    rk[i] = cnt[(int)s[i]] - 1;

	for(int w = 1; w < len; w<<=1)

	{

		for(int i = 0; i < len; i++)

		{

			if(i + w >= len)

			    k2[i] = 0;

			else

			    k2[i] = rk[i + w];

			k1[i] = rk[i];

		}

		for(int i = 0; i < m; i++)

		    cnt[i] = 0;

		for(int i = 0; i < len; i++)

		    cnt[k2[i]]++;

		for(int i = 1; i < m; i++)

		    cnt[i] += cnt[i - 1];

		for(int i = len - 1; i >= 0; i--)

		    psa[--cnt[k2[i]]] = i;

		for(int i = 0; i < m; i++)

		    cnt[i] = 0;

		for(int i = 0; i < len; i++)

		    cnt[k1[i]]++;

		for(int i = 1; i < m; i++)

		    cnt[i] += cnt[i - 1];

		for(int i = len - 1; i >= 0; i--)

		    sa[--cnt[k1[psa[i]]]] = psa[i];

		int pos = 1;

		rk[sa[0]] = 1;

		for(int i = 1; i < len; i++)

		    if(k1[sa[i]] == k1[sa[i - 1]] && k2[sa[i]] == k2[sa[i - 1]])

			    rk[sa[i]] = pos;

			else

			    rk[sa[i]] = ++pos;

		if(pos == len)

		    break;

	}

	for(int i = 0; i < len; i++)

	    rk[sa[i]] = i;

	for(int i = 0; i < len; i++)

	    if(sa[i] < n)

	        printf("%c", s[(sa[i] + n - 1)]);

	return 0;

}

巴特西

2022春每日一题：Day 18

题目：[JSOI2007]字符加密

最新文章

热门文章