专栏首页数据结构与算法P3809 【模版】后缀排序

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 条评论
登录 后参与评论

相关文章

  • BZOJ4698: Sdoi2008 Sandy的卡片(二分 hash)

    attack
  • P3374 【模板】树状数组 1 单点修改与区间查询

    题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某一个数加上x 2.求出某区间每一个数的和 输入输出格式 输入格式: 第一行包含两个整数N...

    attack
  • 洛谷P5245 【模板】多项式快速幂(多项式ln 多项式exp)

    attack
  • LeetCode第五天

    leetcode 第五天 2018年1月6日 22.(566) Reshape the Matrix ? ? JAVA class Solution { ...

    郭耀华
  • LeetCode 215. Kth Largest Element in an Array分析

    显然最简单的思想就是排序,然后取出倒数第k个元素就可以了,我们可以直接调用内部的排序函数。

    desperate633
  • 算法原理系列:木桶排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 高仿京东金融的数值滚动尺

    以前博客讲的大部分都是静态的自定义View的编写,其实无非就是“画画”画出一个好看的效果,而这篇博客写的是写一个动态的自定义控价,这里不仅需要"画",还要各种事...

    HelloJack
  • BZOJ4698: Sdoi2008 Sandy的卡片(二分 hash)

    attack
  • 洛谷P4197 Peaks(Kruskal重构树 主席树)

    考虑把Kruskal重构树建出来,重构树上每个新的节点代表的是边权,同时用倍增数组维护出跳2^i步后能走到的值最大的节点

    attack
  • 浙大版《C语言程序设计(第3版)》题目集 习题6-2 使用函数求特殊a串数列和

    给定两个均不超过9的正整数a和n,要求编写函数求a+aa+aaa++⋯+aa⋯a(n个a)之和。

    C you again 的博客

扫码关注云+社区

领取腾讯云代金券