首页 > 编程语言 > 详细

P3809 【模板】后缀排序

时间:2019-08-28 21:30:36      阅读:67      评论:0      收藏:0      [点我收藏+]

题面

https://www.luogu.org/problem/P3809

题解

好像写的时候还不理解,但是现在理解了。

排序是间接排序,求前缀和,再一个一个减回去。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 1000050
#define ri register int

using namespace std;
char s[N];
int n,m;
int sa[N],rank[N],tp[N],tax[N];

void cntsort(){
  for (ri i=0;i<=m;i++) tax[i]=0;
  for (ri i=1;i<=n;i++) tax[rank[i]]++;
  for (ri i=1;i<=m;i++) tax[i]+=tax[i-1];
  for (ri i=n;i>=1;i--) sa[tax[rank[tp[i]]]--]=tp[i]; /**/
}

void Suffixsort(){
  m=75;
  for (ri i=1;i<=n;i++) rank[i]=s[i]-0+1,tp[i]=i; /**/
  cntsort();
  for (ri w=1,p=0;p<n;m=p,w<<=1) {
    p=0;
    for (ri i=1;i<=w;i++) tp[++p]=n-w+i;
    for (ri i=1;i<=n;i++) if (sa[i]>w) tp[++p]=sa[i]-w;
    cntsort();
    swap(tp,rank); // tp rank not tp sa
    rank[sa[1]]=p=1; // low
    for (ri i=2;i<=n;i++) { // 2
      rank[sa[i]]=(tp[sa[i-1]]==tp[sa[i]] && tp[sa[i-1]+w]==tp[sa[i]+w]) ? p : ++p;
    }
  }
}

int main(){
  scanf("%s",s+1);
  n=strlen(s+1);
  Suffixsort();
  //cout<<n<<endl;
  for (ri i=1;i<=n;i++) printf("%d ",sa[i]);
}

 

P3809 【模板】后缀排序

原文:https://www.cnblogs.com/shxnb666/p/11426303.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!