题解 P3809 【【模板】后缀排序】

_**关于后缀数组**_ ------------ 后缀数组思路其实....不是非常难（炒鸡easy） 这里讲讲倍增算法 [可以在这里看一看经典思路图](https://blog.csdn.net/yxuanwkeith/article/details/50636898) 但是代码实现就特别难受... 三四个数组嵌套很难懂 所以发一篇自己大概（100%）看懂的代码 思路大概是 先基数排序 然后一层for（更新第二关键字（tp）；利用这一轮的第一关键字更新下一轮的&&离散第一关键字（rk）） 当离散出来的计数==长度（n）是就o**k了 上代码！ ```cpp #include <iostream> #include <cstdio> #include <cstring> #define inv inline void #define maxN 1000010 using namespace std; char s[maxN]; //s是字符串的读入 int a[maxN],rk[maxN],sa[maxN],tp[maxN],tax[maxN],n,m; //a是暂存数组，rk（第一关键字）第i位的排名，sa是排名为i的位置，tp是第二关键字辅助用的，tax是桶数组； inv read(){ scanf("%s",&s); n=strlen(s); for(int i=0;i<n;i++) a[i+1]=s[i]; //读入 } inv Rsort(){ for(int i=0;i<=m;i++) tax[i]=0; //tax是桶 //tax清零 for(int i=1;i<=n;i++) tax[rk[tp[i]]]++; //每一个出现的第一关键字++ for(int i=1;i<=m;i++) tax[i]+=tax[i-1]; //tax中i现在代表这个数至多能排第几位 for(int i=n;i>=1;i--) sa[tax[rk[tp[i]]]--]=tp[i]; //如果是第一遍就先不看这个 //就是把这一轮的sa做出来 //第二轮开始因为tp是按第二关键字进数组的 //所以从后往前来第二关键字肯定比前面小 //所以第一关键字相同时，第二关键字越大排名越后 //所以先拿到最大的值然后-- } inv Suffix(){ for(int i=1;i<=n;i++) rk[i]=a[i],tp[i]=i; //因为是第一轮所以直接用ascii码和位置当关键字； Rsort(); // for(int i=1;i<=n;i++) printf("%d ",sa[i]); for(int k=1;k<=n;k<<=1){ int num; num=0; for(int i=n-k+1;i<=n;i++) tp[++num]=i; //从n-k+1开始，到n的位置的第二关键字都为零，所以先入数组 for(int i=1;i<=n;i++) if(sa[i]>k) tp[++num]=sa[i]-k; //因为sa是排好序的，当sa[i]这个位置大于k时 //sa[i]就会作为别人的第二关键字，因为sa排好序的所以从小往大一个for就ok //所以就把sa[i]-k这个位置先进 //上面这两个for做完后tp就完成了 Rsort(); //再进行一次基数排序 swap(rk,tp); //用tp存下这一轮rk //下面开始更新下一轮rk rk[sa[1]]=1; //sa[1]的rk就是1 num=1; //计数器&&自带更新排名 for(int i=2;i<=n;i++) rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k])?num:++num; //（）里面的是比较第一和第二关键字是否相同 //（）里面的如果成立，就直接等于num //如果不成立就++num并变成num++ if(num==n) break; //如果有n种排名就done了！ m=num; //m代表tp的种类 } return; } int main(){ read(); m=122; Suffix(); for(int i=1;i<=n;i++) printf("%d ",sa[i]); // printf("\n"); // for(int i=1;i<=n;i++) printf("%d ",rk[i]); } ```