社区讨论
关于后缀数组的问题
学术版参与者 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 条回复,欢迎继续交流。
正在加载回复...