今天写了品酒大会，一直90分，后来对着题解调试，发现一直以来写的所有SA都是假的，但在所有题目（包括模版）都能通过!

真代码：

for(int i=1;i<=n;i<<=1) //进行倍增，其中sa是没有重复的，x(第一关键字)是有排名重复的，y(第二关键字)是没有重复的
    {
        int now=0;
        for(int j=n-i+1;j<=n;j++) y[++now]=j; //末尾的(1<<i-1)个因为后面没有字符了，所以已经排好序了，并且第二关键字为空，那么就是第二关键字排名最小的
        for(int j=1;j<=n;j++) if(sa[j]>i) y[++now]=sa[j]-i; //这里是在枚举j能否作为sa[j]-(1<<i-1)的第二关键字，
                                                                          //如果可以，那么因为sa是顺序枚举的，sa[j]-(1<<i-1)的第二关键字(也就是j)是当前最小的，故也直接顺序接在后面
        for(int j=1;j<=m;j++) c[j]=0; //清空桶，并进行新一轮基数排序
        for(int j=1;j<=n;j++) c[x[j]]++;
        for(int j=1;j<=m;j++) c[j]+=c[j-1];
        for(int j=n;j;j--) sa[c[x[y[j]]]--]=y[j]; //首先，若第一关键字能比较大小，无论以什么顺序取出元素，其相对位置一定不变。
                                                  //其次，若只能通过第二关键字取出大小，因为先取出来的排名大，所以倒序枚举第二关键字的排名，依照第二关键字的顺序取出桶内的元素
        memcpy(y,x,sizeof(x)); //这里只是为了储存x的原值，没有其他意思
        now=0;
        for(int j=1;j<=n;j++)
            if(y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i]) //和前一个比较，如果第一关键字相同，第二关键字也相同，那么我们就认定在(1<<i+1)中，sa[i]和sa[i-1]的第一关键字相同
                x[sa[j]]=now;
            else
                x[sa[j]]=++now;
        m=now; //因为第一关键字有了now个不同的值，所以值域也要相应变大
        if(n<=m) break; //已经分出，直接退出
    }

假代码：

 for(int i=1;(1<<i)<=n;i++) //进行倍增，其中sa是没有重复的，x(第一关键字)是有排名重复的，y(第二关键字)是没有重复的
    {
        int now=0;
        for(int j=n-(1<<i-1)+1;j<=n;j++) y[++now]=j; //末尾的(1<<i-1)个因为后面没有字符了，所以已经排好序了，并且第二关键字为空，那么就是第二关键字排名最小的
        for(int j=1;j<=n;j++) if(sa[j]>(1<<i-1)) y[++now]=sa[j]-(1<<i-1); //这里是在枚举j能否作为sa[j]-(1<<i-1)的第二关键字，
                                                                          //如果可以，那么因为sa是顺序枚举的，sa[j]-(1<<i-1)的第二关键字(也就是j)是当前最小的，故也直接顺序接在后面
        for(int j=1;j<=m;j++) c[j]=0; //清空桶，并进行新一轮基数排序
        for(int j=1;j<=n;j++) c[x[j]]++;
        for(int j=1;j<=m;j++) c[j]+=c[j-1];
        for(int j=n;j;j--) sa[c[x[y[j]]]--]=y[j]; //首先，若第一关键字能比较大小，无论以什么顺序取出元素，其相对位置一定不变。
                                                  //其次，若只能通过第二关键字取出大小，因为先取出来的排名大，所以倒序枚举第二关键字的排名，依照第二关键字的顺序取出桶内的元素
        memcpy(y,x,sizeof(x)); //这里只是为了储存x的原值，没有其他意思
        now=0;
        for(int j=1;j<=n;j++)
            if(y[sa[j]]==y[sa[j-1]]&&y[sa[j]+(1<<i-1)]==y[sa[j-1]+(1<<i-1)]) //和前一个比较，如果第一关键字相同，第二关键字也相同，那么我们就认定在(1<<i+1)中，sa[i]和sa[i-1]的第一关键字相同
                x[sa[j]]=now;
            else
                x[sa[j]]=++now;
        m=now; //因为第一关键字有了now个不同的值，所以值域也要相应变大
        if(n==m) break; //已经分出，直接退出
    }

两份代码唯一的不同之处在于，真代码中用i替换了(1<<i-1)，这样会多跑一次。

但是我很不理解，SA倍增不是对长度为 $2^i$ 的后缀进行排序吗，那么如果 $2^i \ge n$，这次排序不就没有意义吗？

求大佬解答