poj 3581 Sequence

题目大意：求将一个串分成三段再反转后字典序最小。

题目思路：由于题目中说第一个数最大，所以第一切点只要找到最小后缀就可以了，对于剩下的部分，我想到的办法很麻烦，还要求最长公共前缀，分三段比较。网上的方法是将剩余串增倍，因为其实反转后两个串构成一个循环，用加倍的方法可以避免讨论，这样就可以直接用rank比较了。

方法一：

[cpp] 
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<string> 
#include<queue> 
#include<algorithm> 
#include<vector> 
#include<stack> 
#include<list> 
#include<iostream> 
#include<map> 
using namespace std; 
#define inf 0x3f3f3f3f 
#define M 210000 
int max(int a,int b) 
{ 
    return a>b?a:b; 
} 
int min(int a,int b) 
{ 
    return a<b?a:b; 
} 
int rank[M],height[M],sa[M]; 
int ts[M],tv[M],ta[M],tb[M],r[M],mm[M],dp[20][M]; 
bool cp(int a,int b) 
{ 
    return r[a]<r[b]; 
} 
bool cmp(int *y,int a,int b,int l) 
{ 
    return y[a]==y[b]&&y[a+l]==y[b+l]; 
} 
void da(int n) 
{ 
    int i,j,*x=ta,*y=tb,m,p; 
 
    for(i=0;i<n;i++) y[i]=i; 
    sort(y,y+n,cp); 
    for(i=0;i<n;i++) sa[i]=y[i]; 
    x[sa[0]]=0; 
    p=1; 
    for(i=1;i<n;i++) 
    { 
        if(r[sa[i]]==r[sa[i-1]]) x[sa[i]]=p-1; 
        else x[sa[i]]=p++; 
    } 
    m=p; 
    for(j=1,p=1;p<n;j*=2,m=p) 
    { 
        p=0; 
        for(i=n-j;i<n;i++) y[p++]=i; 
        for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j; 
        for(i=0;i<m;i++) ts[i]=0; 
        for(i=0;i<n;i++) tv[i]=x[y[i]]; 
        for(i=0;i<n;i++) ts[tv[i]]++; 
        for(i=1;i<m;i++) ts[i]+=ts[i-1]; 
        for(i=n-1;i>=0;i--) sa[--ts[tv[i]]]=y[i]; 
        swap(x,y); 
        p=1; 
        x[sa[0]]=0; 
        for(i=1;i<n;i++) 
        { 
            if(cmp(y,sa[i-1],sa[i],j)) x[sa[i]]=p-1; 
            else x[sa[i]]=p++; 
        } 
    } 
} 
void calh(int n) 
{ 
    int i,k; 
    for(i=1;i<=n;i++) rank[sa[i]]=i; 
    k=0; 
    for(i=0;i<n;i++) 
    { 
       int tmp=sa[rank[i]-1]; 
       for(;r[i+k]==r[tmp+k];k++) 
       ; 
       height[rank[i]]=k; 
       k?--k:0; 
    } 
} 
void initrmp(int n) 
{ 
    int i,j,tmp; 
    mm[0]=-1; 
    for(i=1;i<=n;i++) mm[i]=(i&(i-1))?mm[i-1]:mm[i-1]+1; 
    for(i=1;i<=n;i++) dp[0][i]=height[i]; 
    for(i=1;i<=mm[n];i++) 
    { 
        tmp=1<<(i-1); 
        for(j=1;j<=n&&j+tmp<=n;j++) 
        dp[i][j]=min(dp[i-1][j],dp[i-1][j+tmp]); 
    } 
} 
int lcp(int a,int b) 
{ 
    a=rank[a],b=rank[b]; 
    if(a>b) swap(a,b); 
    a++; 
    int l=mm[b-a+1]; 
    b-=(1<<l)-1; 
    return min(dp[l][a],dp[l][b]); 
} 
int main() 
{ 
    int i,n,st1; 
    scanf("%d",&n); 
    for(i=n-1;i>=0;i--) 
    { 
        scanf("%d",&r[i]); 
    } 
    r[n]=-inf; 
    da(n+1); 
 
    calh(n); 
    initrmp(n); 
    int mi=inf; 
    for(i=2;i<n;i++) 
    { 
        if(rank[i]<mi) 
        { 
            mi=rank[i]; 
            st1=i; 
        } 
    } 
    int rec=1; 
    for(i=2;i<st1;i++) 
    { 
        if(lcp(rec,i)<st1-i) 
        { 
            if(rank[i]<rank[rec]) 
                rec=i; 
        } 
        else 
        { 
            if(lcp(rec+(st1-i),0)<i-rec) 
            { 
                if(rank[0]<rank[rec+st1-i]) 
                    rec=i; 
            } 
            else 
            { 
                if(rank[i-rec]<rank[0]) 
                    rec=i; 
            } 
        } 
    } 
    for(i=st1;i<n;i++) 
        printf("%d/n",r[i]); 
    for(i=rec;i<st1;i++) 
        printf("%d/n",r[i]); 
    for(i=0;i<rec;i++) 
        printf("%d/n",r[i]); 
} 
方法二：

[cpp] 
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<string> 
#include<queue> 
#include<algorithm> 
#include<vector> 
#include<stack> 
#include<list> 
#include<iostream> 
#include<map> 
using namespace std; 
#define inf 0x3f3f3f3f 
#define M 410000 
int max(int a,int b) 
{ 
    return a>b?a:b; 
} 
int min(int a,int b) 
{ 
    return a<b?a:b; 
} 
int rank[M],height[M],sa[M]; 
int ts[M],tv[M],ta[M],tb[M],r[M],mm[M],dp[20][M]; 
bool cp(int a,int b) 
{ 
    return r[a]<r[b]; 
} 
bool cmp(int *y,int a,int b,int l) 
{ 
    return y[a]==y[b]&&y[a+l]==y[b+l]; 
} 
void da(int n) 
{ 
    int i,j,*x=ta,*y=tb,m,p; 
 
    for(i=0;i<n;i++) y[i]=i; 
    sort(y,y+n,cp); 
    for(i=0;i<n;i++) sa[i]=y[i]; 
    x[sa[0]]=0; 
    p=1; 
    for(i=1;i<n;i++) 
    { 
        if(r[sa[i]]==r[sa[i-1]]) x[sa[i]]=p-1; 
        else x[sa[i]]=p++; 
    } 
    m=p; 
    for(j=1,p=1;p<n;j*=2,m=p) 
    { 
        p=0; 
        for(i=n-j;i<n;i++) y[p++]=i; 
        for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j; 
        for(i=0;i<m;i++) ts[i]=0; 
        for(i=0;i<n;i++) tv[i]=x[y[i]]; 
        for(i=0;i<n;i++) ts[tv[i]]++; 
        for(i=1;i<m;i++) ts[i]+=ts[i-1]; 
        for(i=n-1;i>=0;i--) sa[--ts[tv[i]]]=y[i]; 
        swap(x,y); 
        p=1; 
        x[sa[0]]=0; 
        for(i=1;i<n;i++) 
        { 
            if(cmp(y,sa[i-1],sa[i],j)) x[sa[i]]=p-1; 
            else x[sa[i]]=p++; 
        } 
    } 
} 
void calh(int n) 
{ 
    int i,k; 
    for(i=1;i<=n;i++) rank[sa[i]]=i; 
    k=0; 
    for(i=0;i<n;i++) 
    { 
       int tmp=sa[rank[i]-1]; 
       for(;r[i+k]==r[tmp+k];k++) 
       ; 
       height[rank[i]]=k; 
       k?--k:0; 
    } 
} 
int main() 
{ 
    int i,n,st1; 
    scanf("%d",&n); 
    for(i=n-1;i>=0;i--) 
    { 
        scanf("%d",&r[i]); 
    } 
    r[n]=-inf; 
    da(n+1); 
    calh(n); 
    int mi=inf; 
    for(i=2;i<n;i++) 
    { 
        if(rank[i]<mi) 
        { 
            mi=rank[i]; 
            st1=i; 
        } 
    } 
    for(i=st1;i<n;i++) 
        printf("%d/n",r[i]); 
    int rec=1; 
    for(i=0;i<st1;i++) 
    { 
        r[i+st1]=r[i]; 
    } 
    r[2*st1]=-inf; 
    da(st1*2+1); 
    calh(2*st1); 
    mi=inf; 
    for(i=1;i<st1;i++) 
    { 
        if(rank[i]<mi) 
        { 
            mi=rank[i]; 
            rec=i; 
        } 
    } 
    for(i=rec;i<st1+rec;i++) 
    { 
        printf("%d/n",r[i%st1]); 
    } 
} 

作者：Wings_of_Liberty