4326268_ac_1375ms_5688k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include<stdio.h>
#include<string.h>
#include<algorithm>
const int maxn = 200005;
using namespace std;
struct node
{
    int x;
    int id;
}arry[200003];

int num[200003];
int Init[200003];
int h[maxn], smem[3][maxn];
int *SA, *nSA, *Rank, *nRank;
int c[1000005];
int MAX, n;
bool cmp( node a, node b )
{
    if( a.x < b.x )return true;
    else return false;
}
void suffix_array()
{
int i, j, k;
SA=smem[0], nSA=smem[1], Rank=smem[2];
for( i = 0; i <= MAX; i++ )c[i] = 0;
for( i = 0; i < n; i++ ) c[num[i]]++;
for( i = 1; i <= MAX; i++ ) c[i]+=c[i-1];
for( i = 0; i < n; i++ ) SA[--c[num[i]]]=i;
for( Rank[SA[0]] = 0,i = 1; i < n; i++ )
{
   Rank[SA[i]] = Rank[SA[i-1]];
   if( num[SA[i-1]] != num[SA[i]] )
    Rank[SA[i]]++;
}
for( k = 1; k < n && Rank[ SA[n-1] ] < n-1; k *= 2 )
{
   for( i = 0; i < n;i++ )c[Rank[SA[i]]] = i+1;
   for( i = n-1; i >= 0;i-- )
   {
    if( SA[i] >= k )
    {
     nSA[ --c[Rank[SA[i]-k]] ] = SA[i]-k;
            }
        }
   for( i = n-k; i < n; i++ )
   {
    nSA[ --c[Rank[i]] ] = i;
        }
   nRank = SA, SA = nSA;
   for( nRank[SA[0]] = 0, i = 1; i < n; i++ )
   {
    nRank[SA[i]] = nRank[SA[i-1]];
    if( Rank[SA[i]] != Rank[SA[i-1]] || Rank[SA[i]+k] != Rank[SA[i-1]+k] )
    {
     nRank[SA[i]]++;
            }
   }
   nSA = Rank; 
        Rank = nRank;
}
}

void work()
{
    int i;
    suffix_array();
    int min = Rank[2];
    int ans = 2;
    for( i = 3; i < n; i++ )
    {
        if( min > Rank[i] )
        {
            min = Rank[i];
            ans = i;
        }
    }
    for( i = ans; i < n; i++ )
    {
        printf( "%d\n", arry[Init[num[i]]].x );
    }
    n = ans;
    suffix_array();
    int second = Rank[1];
    int anss = 1;
    for( i = 2; i < ans; i++ )
    {
        if(second > Rank[i] )
        {
            second = Rank[i];
            anss = i;
        }   
    }
    for( i = anss; i < ans; i++ )
    {
        printf( "%d\n", arry[Init[num[i]]].x );
    } 
    for( i = 0; i < anss; i++ )
    {
        printf( "%d\n", arry[Init[num[i]]].x ); 
    }
}
int main()
{
    int i;
    scanf( "%d", &n );
    {
        for( i = n-1; i >= 0; i-- )
        {
            scanf( "%d", &arry[i].x );
            arry[i].id = i;
        }
        sort(arry,arry+n,cmp);
        int top = 1;
        num[arry[0].id] = 1;
        Init[1] = 0;
        for( i = 1; i < n; i++ )
        {
            if( arry[i].x == arry[i-1].x )
            {             
                num[arry[i].id] = top;
            }
            else
            {
                num[arry[i].id] = ++top;
            }
            Init[top] = i;
        }
        MAX = top;    
        work();
    } 
    return 0;
}