做中国旅游网站的目的与必要性,龙之向导的发展前景,在北京注册公司要哪些条件,长沙百度提升优化【题目来源】https://www.luogu.com.cn/problem/P3809【题目描述】 读入一个长度为 n 的由大小写英文字母或数字组成的字符串#xff0c;请把这个字符串的所有非空后缀按字典序#xff08;用 ASCII 数值比较#xff09;从小到大排序#xff0c;然后按顺序输出后缀的第一个字…【题目来源】https://www.luogu.com.cn/problem/P3809【题目描述】 读入一个长度为 n 的由大小写英文字母或数字组成的字符串请把这个字符串的所有非空后缀按字典序用 ASCII 数值比较从小到大排序然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 1 到 n。【输入格式】 一行一个长度为 n 的仅包含大小写英文字母或数字的字符串。【输出格式】 一行共 n 个整数表示答案。【输入样例】 ababa【输出样例】 5 3 1 4 2【说明/提示】 1≤n≤10^6【算法分析】 ● 后缀数组简介详见https://blog.csdn.net/hnjzsyjyj/article/details/138695966● 倍增法求后缀数组的算法用到如下 3 个数组 1后缀数组 sa[i]排第几的是谁← 后缀数组中的第 i 个元素是从第几个字符开始的后缀 2名次数组 rk[i]你排第几← 从第 i 个字符开始的后缀在后缀数组中排第几 3lcp[] 数组表示后缀 sa[i] 与 sa[i−1] 的最长公共前缀的长度。更常表述为 height[] 数组。 ● sa[] 与 rk[] 是一一对应关系互为逆运算。即存在关系 sa[rk[i]]i 及 rk[sa[i]]i。【算法代码】
#include bits/stdc.h
using namespace std;const int maxn1e65;//sa[i] 排第几的是谁
//rk[i] 你排第几
//height[i] 表示后缀sa[i]与sa[i-1]的最长公共前缀的长度
//fi[i] 表示第i个后缀的第一关键字
//se[i] 表示第i个后缀的第二关键字
//c[i] 表示关键字为i的数的个数
int sa[maxn],rk[maxn];
int fi[maxn],se[maxn],c[maxn];char s[maxn];
int n,m;void get_sa() {for(int i1; in; i) c[fi[i]s[i]];for(int i2; im; i) c[i]c[i-1]; //prefix sumfor(int in; i1; i--) sa[c[fi[i]]--]i;for(int k1; kn; k1) {//Radix Sort based on 2nd keyint num0;for(int in-k1; in; i) se[num]i;for(int i1; in; i)if(sa[i]k) se[num]sa[i]-k;//Radix Sort based on 1st keyfor(int i1; im; i) c[i]0;for(int i1; in; i) c[fi[i]];for(int i2; im; i) c[i]c[i-1];for(int in; i1; i--) sa[c[fi[se[i]]]--]se[i], se[i]0;//Discretize all sorted suffixes according to the first 2K charactersswap(fi,se);fi[sa[1]]1, num1;for(int i2; in; i) {if(se[sa[i]]se[sa[i-1]] se[sa[i]k]se[sa[i-1]k]) fi[sa[i]]num;else fi[sa[i]]num;}if(numn) break;mnum;}
}int main() {scanf(%s, s1);nstrlen(s1);m122; //ASCII of z is 122get_sa();for(int i1; in; i) printf(%d ,sa[i]);printf(\n);return 0;
}/*
in:
ababaout:
5 3 1 4 2
*/【参考文献】https://oi-wiki.org/string/sa/https://www.cnblogs.com/heyujun/p/10300582.htmlhttps://blog.csdn.net/hnjzsyjyj/article/details/138695966https://zhuanlan.zhihu.com/p/649662771https://zhuanlan.zhihu.com/p/549744336https://www.cnblogs.com/zwfymqz/p/8413523.htmlhttps://www.cnblogs.com/Aya-Uchida/p/11361472.html
