首页 / 更多教程 / _bzoj1031 [JSOI2007]字符加密Cipher【后缀数组】

_bzoj1031 [JSOI2007]字符加密Cipher【后缀数组】

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了_bzoj1031 [JSOI2007]字符加密Cipher【后缀数组】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1434字，纯文字阅读大概需要3分钟。

内容图文

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1031

保存后缀数组模版。

其实如果数据范围小一点，或者空间限制再大一点，或者甚至只要字母表再小一点就可以使用后缀自动机了，只可惜空间不允许，就用后缀数组！

其实还是不是很理解代码，是否该当成黑盒代码背下来呢？

#include <cstdio>
#include <cstring>
#include <algorithm>

const int maxn = 200005;

int n, mx, sa[maxn], t1[maxn], t2[maxn], c[maxn], *x, *y;
char s[maxn];

int main(void) {
	scanf("%s", s);
	n = strlen(s);
	memcpy(s + n, s, n - 1);
	n = (n << 1) - 1;
	x = t1;
	y = t2;
	mx = 128;
	
	memset(c, 0, sizeof c);
	for (int i = 0; i < n; ++i) {
		++c[x[i] = s[i]];
	}
	for (int i = 1; i < mx; ++i) {
		c[i] += c[i - 1];
	}
	for (int i = n - 1; ~i; --i) {
		sa[--c[x[i]]] = i;
	}
	int p;
	for (int k = 1; k <= n; k <<= 1) {
		p = 0;
		for (int i = n - k; i < n; ++i) {
			y[p++] = i;
		}
		for (int i = 0; i < n; ++i) {
			if (sa[i] >= k) {
				y[p++] = sa[i] - k;
			}
		}
		
		memset(c, 0, sizeof c);
		for (int i = 0; i < n; ++i) {
			++c[x[y[i]]];
		}
		for (int i = 0; i < mx; ++i) {
			c[i] += c[i - 1];
		}
		for (int i = n - 1; ~i; --i) {
			sa[--c[x[y[i]]]] = y[i];
		}
		
		std::swap(x, y);
		p = 1;
		x[sa[0]] = 0;
		for (int i = 1; i < n; ++i) {
			x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]? p - 1: p++;
		}
		if (p >= n) {
			break;
		}
		mx = p;
	}
	
	int tem = (n + 1) >> 1;
	for (int i = 0; i < n; ++i) {
		if (sa[i] < tem) {
			printf("%c", s[sa[i] + tem - 1]);
		}
	}
	return 0;
}

原文：http://www.cnblogs.com/ciao-sora/p/6166065.html

内容总结

以上是互联网集市为您收集整理的_bzoj1031 [JSOI2007]字符加密Cipher【后缀数组】全部内容，希望文章能够帮你解决_bzoj1031 [JSOI2007]字符加密Cipher【后缀数组】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1273246.html

来源：【匿名】