P3809 【模版】后缀排序

题目背景

这是一道模版题。

题目描述

读入一个长度为 nn 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 11 到 nn。

输入输出格式

输入格式:

一行一个长度为 nn 的仅包含大小写英文字母或数字的字符串。

输出格式:

一行,共n个整数,表示答案。

输入输出样例

输入样例#1:

ababa

输出样例#1:

5 3 1 4 2

说明

n <= 10^6n<=10​6​​

看了一下午的后缀数组

基数排序的思想我懂啊。,

倍增的思想我懂啊。。

后缀数组的思想我也懂啊。。

为毛代码一行都看不懂啊。。。。。。。。。。。。。。。。。。。。。。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 const int MAXN=1000001;
 8 void read(int &n)
 9 {
10     char c='+';int x=0;bool flag=0;
11     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
12     while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
13     flag==1?n=-x:n=x;
14 }
15 int tax[MAXN];// 基数排序的辅助数组
16 int tp[MAXN];//基数排序的第二关键字
17 int a[MAXN];// 字符串数组
18 int sa[MAXN];//
19 int rak[MAXN]; 
20 int n,m;
21 void qsort()
22 {
23     for(int i=0;i<=m;i++)    tax[i]=0;
24     for(int i=1;i<=n;i++)    tax[rak[tp[i]]]++;
25     for(int i=1;i<=m;i++)    tax[i]+=tax[i-1];
26     for(int i=n;i>=1;i--)    sa[tax[rak[tp[i]]]--]=tp[i];
27 }
28 int comp(int *f,int x,int y,int l)
29 {
30     return (f[x]==f[y]&&f[x+l]==f[y+l]);
31 }
32 void suffix_ar()
33 {
34     for(int i=1;i<=n;i++)
35         rak[i]=a[i],tp[i]=i;
36     m=127,qsort();
37     for(int w=1,p=1,i;p<n;w+=w,m=p)
38     {
39         for(p=0,i=n-w+1;i<=n;i++)
40             tp[++p]=i;
41         for(int i=1;i<=n;i++)
42             if(sa[i]>w)
43                 tp[++p]=sa[i]-w;
44         qsort(),swap(rak,tp),rak[sa[1]]=p=1;
45         for(int i=2;i<=n;i++)
46             rak[sa[i]]=comp(tp,sa[i],sa[i-1],w)? p:++p;
47     }
48     for(int i=1;i<=n;i++)
49         printf("%d ",sa[i]);
50 }
51 int main()
52 {
53     string s;
54     cin>>s;
55     n=s.length();
56     for(int i=0;i<(s.length());i++)
57         a[i+1]=s[i]-48;
58     suffix_ar();
59     return 0;
60 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

数组

1、 一维数组的定义和使用 通过对前面知识的学习,我们已经知道如何定义和使用一个一个的各种变量,但总有不够用的时候。举个例子,我要记录一个班32个同学C语...

41980
来自专栏GreenLeaves

Oracle dbms_random随机函数包

dbms_random是oracle提供的一个随机函数包,以下是它的一些常用的功能: 1、dbms_random.value 作用:生成一个大于等于0,大于等于...

21950
来自专栏漫漫深度学习路

pytorch学习笔记(十七):python 端扩展 pytorch

pytorch 虽然提供了很多的 op 使得我们很容易的使用。但是当已有的 op 无法满足我们的要求的时候,那就需要自己动手来扩展。 pytorch 提供了两种...

31070
来自专栏Jed的技术阶梯

图解冒泡排序

在上面实现的代码中,即使n个数本来就是有序的,也会进行(n-1)次排序(只比较,不交换) 优化:当数组已经有序后,就中断循环

20730
来自专栏wym

18年暑假多校赛第一场 1004

题目地址http://acm.hdu.edu.cn/showproblem.php?pid=6301

8420
来自专栏好好学java的技术栈

“365算法每日学计划”:05打卡-图解冒泡排序(多解法)

11930
来自专栏韦弦的偶尔分享

Swift 两数之和 - LeetCode

12020
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题31连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组和的最大值。要求时间复杂度为O(n) 分析:统计连续子数...

30790
来自专栏数据结构与算法

BZOJ2212: [Poi2011]Tree Rotations(线段树合并)

可以证明,对于\(m\)个仅有一个元素,权值范围在\([1, n]\)的线段树合并的复杂度为\(mlogn\)

8120
来自专栏小樱的经验随笔

51 Nod 1791 合法括号子段【分治+字符串】

1791 合法括号子段 基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题 有一个括号序列,现在要计算一下它有多少非空子段是合法...

30860

扫码关注云+社区

领取腾讯云代金券