额,最近在听大佬讲题的时候学的（因为听不懂）

具体是学的远航之曲大佬的blog。百度上也有就不放链接了。

我要在此立下一个flag。我一定要自己将这一部分重写一边。

然后又是和其他人一样的什么从蒟蒻的角度出发，什么自己的感想，什么史上最详细。

然而我并不想这么说。也不想、、、

我只是想写一点感性的东西。

先说一下SA的基数排序。我觉得，就是一个双关键字排序的思想。现按第一关键字排序，相同第一关键字按第二关键字排序。

然后就是为什么可以倍增。我们先想一想，对于相同长度的字符串，他们的相对大小是一定的。而且我们字符串是按位比较的。

就是说第一大的字符串接在第二大的字符串后，总比反过来接大。 所以我们不必要计较数值的大小，那只是一个暂时的，只是表示相对关系的数值。

对于没有比较的部位也不要瞎想。根据字符串的比较方式。如果还没有比较到后面就已经不一样了。那么后面的位置就对大小没有影响了。可以回忆一下基数排序的方法。

然后就是代码

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int maxn=1010000;char data[maxn];//输入的字符串int rank[maxn];//下标为i的排名int tot[maxn];//排名个数的前缀和int sa[maxn];//后缀数组int pas[maxn];//临时使用的变量int lcp[maxn];//lcp：第i大的后缀和第i+1大的最长的前缀int n,m;//长度  多少中不同的排名void build_Sa(){    n=strlen(data),m=150;//一开始排名总数开大    for(int i=0;i
        
         =0;i--)        sa[--tot[rank[i]]]=i;//这里是一个小难点                //为什么可以这样： 首先我们知道，拥有同一个rank的后缀的数量是一定的，所以不会越界                //为什么要这样，因为插入的顺序在SA数组中是不定序的，为了快速的插入需要我们预先划定出来在哪里插    for(int k=1;k<=n;k<<=1)//，枚举处理长度    {        int num=0;        for(int i=n-k;i
         
          =k) pas[num++]=sa[i]-k;//同样是储存第一关键字 //首先我们在处理第二关键字的时候也是顺序的，所以大小也是顺序的，又因为下标同减一个常数，所以第一关键字也是递增的 for(int i=0;i<=m;i++) tot[i]=0;//排名前缀和清零 for(int i=0;i
          
           =0;i--) sa[--tot[rank[pas[i]]]]=pas[i],pas[i]=0//又是一个难点 //首先我们来看遍历顺序，是逆序的。然后我们又保证了pas数组中相同第一关键字的变量他们储存的顺序是按照第二关键字递增的（其实如果不考虑补0的后缀，整个pas数组还是按照第一个关键字递增的） //所以我们在遍历的时候，最先被遍历的，一定是在第一关键字相同的变量中最大的; swap(pas,rank);//交换，算排序后的rank num=1;rank[sa[0]]=1; for(int i=1;i
           
            =n) break; m=num; }}void build_LCP(){ int h=0; for(int i=0;i