社区讨论

关于后缀数组的问题

学术版参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@locz4n0d
此快照首次捕获于
2023/10/30 22:06
2 年前
此快照最后确认于
2023/11/05 08:27
2 年前
查看原帖
CPP

	void SA(char *s, int *sa, int *rank, int n, int m) {
		int ws[1000005], t[1000005], *x = rank, *y = t;
		for (int i = 0; i < m; ++i) ws[i] = 0;
		for (int i = 1; i <= n; ++i) ++ws[x[i] = s[i]];
		for (int i = 1; i < m; ++i) ws[i] += ws[i - 1];
		for (int i = n; i >= 1; --i) sa[ws[x[i]]--] = i;
		for (int l = 1, p = 1; p < n; l <<= 1, m = p) {
			p = 0;
			for (int i = n - l + 1; i <= n; ++i) y[++p] = i;
			for (int i = 1; i <= n; ++i) if (sa[i] > l) y[++p] = sa[i] - l;
			for (int i = 0; i < m; ++i) ws[i] = 0;
			for (int i = 1; i <= n; ++i) ++ws[x[i]];
			for (int i = 1; i < m; ++i) ws[i] += ws[i - 1];
			for (int i = n; i >= 1; --i) sa[ws[x[y[i]]]--] = y[i];
			swap(x, y), p = 1, x[sa[1]] = 0;
			for (int i = 2; i <= n; ++i) {
			//	assert(sa[i - 1] + l <= n);
			//	assert(sa[i] + l <= n); 
				x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + l] == y[sa[i] + l] ? p - 1 : p++;    // 为什么很多代码这里都没有判数组越界
			}
		}
	}

回复

4 条回复,欢迎继续交流。

正在加载回复...