洛谷P3809 【模板】后缀排序

• 先来一道最水的模板题o(*≧▽≦)ツ┏━┓
• sa[nmax]  sa[i]     排名为i的数的下标是多少
• x[nmax]    x[i]       值，value,这个每次循环都要根据排名更新一遍
• y[nmax]    y[i]       两次作为中间数组使用，第一次根据sa[i]更新第二关键字排名为i的数第一关键字的位置，第二次更新x[i]（由于比较的时候用到原来x[i]的值，所以先用y[i]更新，最后把y[i]赋值给x[i]）
• qsort()函数   知道了每个数第二关键字的排名（y[i]）和第一个关键字的值（x[i]）求数的排名，用基数排序，结果在sa[i]里面
• 每次循环完的状态： x[i] , sa[i] 已经求出
• 最外层循环的 l :对应当前的sa[i]的l，在本次循环之后sa[i]指代的长度变为 2l
• 所以 l<n （或者<=n/2） 
• 好容易写错啊这个后缀数组。。。代码里是一些容易错的点
• 代码：
  

   1 #include <bits/stdc++.h>
   2 #define nmax 1000010
   3 
   4 using namespace std;
   5 int c[nmax],rk[nmax],sa[nmax],x[nmax],y[nmax];
   6 //y[i]第二关键字排名为i的数第一关键字的位置
   7 
   8 char s[nmax];
   9 int n,k,m=200;
  10 
  11 void qsort(){
  12     for (int i=1; i<=m; i++) c[i]=0;
  13     for (int i=1; i<=n; i++) c[ x[i] ]++;
  14     for (int i=1; i<=m; i++) c[i]+=c[i-1];
  15     for (int i=n; i>=1; i--) sa[ c[ x[y[i]] ]-- ]=y[i];
  16 }
  17 
  18 int main(){
  19     scanf("%s",s+1);
  20     n=strlen(s+1);
  21     for (int i=1; i<=n; i++) x[i]=s[i];
  22     for (int i=1; i<=n; i++) y[i]=i;
  23     qsort();
  24     for (int l=1; l<n; l<<=1) { 
  25         int t=0;
  26         for (int i=n-l+1; i<=n; i++) y[++t]=i; 
  27         //有些数字是没有第一关键字的，有些数字的第二关键字不在sa[i]能覆盖的范围内
  28         for (int i=1; i<=n; i++) if(sa[i]>l) y[++t]=sa[i]-l;  //如果有第一关键字
  29         qsort();
  30         m=1;
  31         y[ sa[1] ]=m;
  32         for (int i=2; i<=n; i++) {
  33             //这里容易错，sa[i]指代的长度有2l，但是x指代的长度只有l，所以第二关键字也要比较
  34             if( x[sa[i]]==x[sa[i-1]] ) if( x[ sa[i]+l ]==x[sa[i-1]+l] ) { y[ sa[i] ]=m; continue; }
  35             y[ sa[i] ]=++m;
  36         }
  37         for (int i=1; i<=n; i++) x[i]=y[i];
  38     }
  39     for (int i=1; i<=n; i++) printf("%d ",sa[i]);
  40     return 0;
  41 }

  (<ゝω?)☆

   

混子的 后缀数组 刷题记录

原文：https://www.cnblogs.com/jiecaoer/p/11609119.html