Infinite Fraction Path HDU 6223 2017沈阳区域赛G题题解

题意：给你一个字符串s，找到满足条件(s[i]的下一个字符是s[(i*i+1)%n])的最大字典序的长度为n的串。

思路：类似后缀数组，每次倍增来对以i开头的字符串排序，复杂度O(nlogn)。代码很多地方借鉴后缀数组。

倍增：比如这次排序好了长度为m的串，那么想扩展为长度为2*m的串则需要用i的排名为第一关键字，i+m的排名为第二关键字进行排序，这种排序正好可以使用基数排序。

下面是代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=155555;
int n;
int m;
int tp[maxn],Rank[maxn],SA[maxn],tax[maxn];
void Rsort()///SA为排名为i的元素所在的位置，tp为第二关键字，Rank作为第一关键字，Rank为i元素的排名。
{
    for(int i=0; i<=m; i++)tax[i]=0;
    for(int i=1; i<=n; i++)tax[Rank[tp[i]]]++;
    for(int i=1; i<=m; i++)tax[i]+=tax[i-1];
    for(int i=n; i>=1; i--)SA[tax[Rank[tp[i]]]--]=tp[i];
}
char st[maxn];
int go[maxn][2];
int main()
{
    int t;
    while(~scanf("%d",&t))
    {
        int c=1;
        while(t--)
        {
            scanf("%d",&n);
            scanf("%s",st+1);
            for(long long i=1; i<=n; i++)
                go[i][0]=((i-1)*(i-1)+1)%n+1;///滚动数组，倍增查找i后面的第2^k的位置。
            m=11;
            for(int i=1; i<=n; i++)
                tp[i]=i,Rank[i]=st[i]-'0';
            int p;
            for(int t=0; t<18&&(1<<t)<=n; t++)
            {
                for(int i=0;i<=m;i++)tax[i]=0;
                for(int i=1; i<=n; i++)tax[Rank[go[i][t&1]]]++;
                for(int i=1;i<=m;i++)tax[i]+=tax[i-1];
                for(int i=1;i<=n;i++)tp[tax[Rank[go[i][t&1]]]--]=i;
                Rsort();
                swap(tp,Rank);
                Rank[SA[1]]=p=1;
                for(int i=2; i<=n; i++)Rank[SA[i]]=(tp[SA[i]]==tp[SA[i-1]]&&tp[go[SA[i]][t&1]]==tp[go[SA[i-1]][t&1]])?p:++p;
                if(Rank[SA[n]]!=Rank[SA[n-1]])break;///剪枝，如果已经能确定最大的了  直接break
                m=p;
                for(int i=1;i<=n;i++)
                    go[i][!(t&1)]=go[go[i][t&1]][t&1];///这里是倍增,go[i]代表i后面第2^t的元素的位置
            }
            printf("Case #%d: ",c++);
            long long loc=SA[n]-1;
            for(int i=0; i<n; i++,loc=(loc*loc+1)%n)
                printf("%c",st[loc+1]);
            puts("");
        }
    }
    return 0;
}