1688代加工官方网站,双流区的规划建设局网站,做企业门户网站,深圳网页设计科技有限公司后缀数组
后缀数组 (SA) 是一种重要的数据结构#xff0c;通常使用倍增或者DC3算法实现#xff0c;这超出了我们的讨论范围。 在本题中#xff0c;我们希望使用快排、Hash与二分实现一个简单的O(nlog2n)的后缀数组求法。 详细地说#xff0c;给定一个长度为 n 的字符串S通常使用倍增或者DC3算法实现这超出了我们的讨论范围。 在本题中我们希望使用快排、Hash与二分实现一个简单的O(nlog2n)的后缀数组求法。 详细地说给定一个长度为 n 的字符串S下标 0~n-1我们可以用整数 k(0≤kn) 表示字符串S的后缀 S(k~n-1)。 把字符串S的所有后缀按照字典序排列排名为 i 的后缀记为 SA[i]。 额外地我们考虑排名为 i 的后缀与排名为 i-1 的后缀把二者的最长公共前缀的长度记为 Height[i]。 我们的任务就是求出SA与Height这两个数组。
输入格式 输入一个字符串其长度不超过30万。 字符串由小写字母构成。
输出格式 第一行为数组SA相邻两个整数用1个空格隔开。 第二行为数组Height相邻两个整数用1个空格隔开我们规定Height[1]0。
输入样例 ponoiiipoi 输出样例 9 4 5 6 2 8 3 1 7 0 0 1 2 1 0 0 2 1 0 2 说实话看到这道题的时候真的是一脸懵这东西咋用hash二分快排。 后来找了些博客看终于理解其中的思路了 一、先记录整条的hash值。 二、用一个sort函数自定义cmp。 三、通过二分确定两个后缀字符之间的前缀相同字母。 这道题写这篇题解的时候又重新去写了一遍感觉真的难。
#includeiostream
#includecstring
#includealgorithm
#includecstdio
using namespace std;
typedef unsigned long long ull;
const int base 131;
const int N 3e5 10;
char str[N];
ull h[N], p[N];
int sa[N], n;
ull gethash(int l, int r) {//得到某一段的hash值return h[r] - h[l - 1] * p[r - l 1];
}
int sumsub(int a, int b) {int l 0, r min(n - a 1, n - b 1);//取最小的。while(l r) {//二分。int mid (l r 1) 1;if(gethash(a, a mid - 1) ! gethash(b, b mid - 1)) r mid - 1;else l mid;}return r;
}
bool cmp(int a, int b) {int l sumsub(a, b);//两个的相同前缀长度。int x a l n ? - 1e9 : str[a l];如果有一个单词都是前缀防止发生数组越界。int y b l n ? - 1e9 : str[b l];return x y;
}
int main() {scanf(%s, str 1);//从第一个字符开始可以避免hash的边界问题。n strlen(str 1);p[0] 1;for(int i 1; i n; i) {h[i] h[i - 1] * base str[i] - a 1;p[i] p[i - 1] * base;sa[i] i;}sort(sa 1, sa n 1, cmp);//对下标进行排序。for(int i 1; i n; i) printf(%d%c, sa[i] - 1, i n ? \n : );printf(0 );for(int i 2; i n; i) printf(%d%c, sumsub(sa[i], sa[i - 1]), i n ? \n : );return 0;
}这个算法耗时还是非常长的并不是真正的能用的算法但是这个写法的综合力度还是比较高的思想还是可以借鉴的。
