下面是我的代码,我的板子在vj上跑过三四道题目,是没有问题的
自测也是没有问题的
为啥呢😔
#if __cplusplus >= 201103L #pragma comment(linker, "/STACK:102400000,102400000") #pragma GCC optimize(3, "Ofast", "inline") #include <bits/stdc++.h> #else #include <algorithm> #include <bitset> #include <cmath> #include <iostream> #include <string.h> #include <vector> #endif using namespace std; #define inf __INT_MAX__ #define enf INT_MIN #define INF LLONG_MAX #define ENF LLONG_MIN const int MAXN = 1e5 + 10; const double pi = acos(-1.0); const double eps = 1e-6; typedef long long ll; typedef unsigned long long ull; #define ***(x) ((x > eps) - (x < -eps)) int s[MAXN]; char ab[MAXN]; int rk[MAXN], sa[MAXN], tax[MAXN], n, m; int tp[MAXN]; //tp第二关键字数组 //rk第一关键字第i位的排名,sa排名第i位的位置 void rsort(int a[], int b[]) { //a第一关键字数组,b第二关键字数组 for (int i = 0; i <= m; i++) //桶清零 tax[i] = 0; for (int i = 1; i <= n; i++) //在第一关键字相同的情况下,按照第二关键字从小到大放入 tax[a[b[i]]]++; for (int i = 1; i <= m; i++) //计算排名 tax[i] += tax[i - 1]; for (int i = n; i >= 1; i--) //在第一关键字相同的情况下,按照第二关键字从大到小取出 sa[tax[a[b[i]]]--] = b[i]; } void suffix() { for (int i = 1; i <= n; i++) //字母大小为第一关键字,位置为第二关键字 rk[i] = s[i], tp[i] = i; rsort(rk, tp); for (int l = 1, num = 0; l <= n && num != n; l <<= 1) { num = 0; for (int i = n - l + 1; i <= n; i++) //在n-l+1后面的位置都无法找到l位后的后续,所以为0 tp[++num] = i; //所以先将位置存入 for (int i = 1; i <= n; i++) //sa[i]=排名i的后缀位置,如果>l,那么它就可以和sa[i]-l位置的第一关键字匹配 if (sa[i] > l) tp[++num] = sa[i] - l; //此刻tp数组内情况:[第二关键字为0的一组的起始位置......第二关键字按照从小到大的一组的起始位置] rsort(rk, tp); //此处分割,上述为k阶段的sa以及排序,下述为k<<1阶段的rk swap(rk, tp); //用tp存储上一轮的rk,来为下一轮的rk做准备 rk[sa[num = 1]] = 1; for (int i = 2; i <= n; i++) //排名相近的第一关键字和第二关键字是否相等 rk[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + l] == tp[sa[i - 1] + l]) ? num : ++num; m = num; } return; } int main() { while (~scanf("%d%s", &n, (ab + 1))) { int pa = -1, pb = -1; for (int i = n; i >= 1; i--) { if (ab[i] == 'a') s[i] = (pa == -1 ? n : pa - i), pa = i; else s[i] = (pb == -1 ? n : pb - i), pb = i; } n++; s[n] = n; m = n; suffix(); for (int i = n - 1; i >= 1; i--) printf("%d ", sa[i]); printf("\n"); } //get_height(); }
全部评论
(1) 回帖