2015年7月4日 星期六

[CF 557E] Ann and Half-Palindrome

作法:

以下記原字串為$S$。首先核心當然就是一個一個確定答案要是$a$還是$b$,或是決定停止加字元並輸出。在確定答案時,一開始答案為空字串,接下來我們必須知道「有多少個半回文子字串的前綴是$a$」,假設有$num$個好了,如果$num\geq k$,那麼可以知道答案的第一個字元會是$a$,否則會是$b$,並且把$k$扣掉$num$後繼續下去(因為當在第一個位子放上$b$的同時答案字串就已經自動大於$num$個半回文子字串了)。另外我們還要知道什麼時候停止繼續加字元,而這只要滿足:假設當前的答案字串為$T$,那麼如果$T$是半回文且他在$S$中的出現次數$\geq k$時,$T$就是我們要的答案,證明並不難。因此我們會需要詢問兩個東西,一個是「給定某個字串$T$,問$S$中有幾個半回文子字串使得他的前綴是$T$」,另一個則是「給定某個字串$T$,問他是否為半回文,並且知道他在$S$裡出現了幾次」。並且這些詢問頂多$O(n)$次。後者中問半回文就直接$O(n)$判斷,在$S$裡出現幾次則用個後綴數組來作就可以了。至於前者比較麻煩,我們考慮先用後綴數組找出所有$T$在$S$裡出現的位置,假設對於某個$i$,$S[i,...,i+|T|-1]$和$T$字串一模一樣,那我們想知道的是有幾個$j$滿足:$j\geq i$,並且$S[i,...,j]$為半回文。這個東西就是某種後綴和,也就是我們如果可以先得出所有的$S$的子字串$S[i,...,j]$是否為半回文,用個二維陣列紀錄起來,再對第二維作後綴和(前綴和也可以),就可以$O(1)$詢問前面所需要的東西了。而這個二維陣列的求法就類似回文的想法,因為對於所有同一個中心點的$S$的子字串來說,設他從中心往左往右的長度為$L$,那麼只考慮所有$L$的奇偶性相同且同中心點的子字串,那麼當長度比較小的不是半回文時,長度比較大的也不是,因此只要枚舉中心點和字串半長度的奇偶性,從中間往外跑就可以了。

code :



#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10 ;
 
namespace SufArr
{
    int n ;
    char s[maxn] ;
    int sa[maxn],rank[maxn],rank2[maxn],cnt[maxn],pri[maxn] ;
    int height[maxn] ;
    const int LOG=(int)(log2(maxn)+1) ;
 
    void init(char *_s)
    {
        n=strlen(_s)+1 ;
        for(int i=0;i<n;i++) s[i]=_s[i] ;
    }
 
    void build_sa(int m='z'+1)
    {
        for(int i=0;i<m;i++) cnt[i]=0 ;
        for(int i=0;i<n;i++) cnt[rank[i]=s[i]]++ ;
        for(int i=1;i<m;i++) cnt[i]+=cnt[i-1] ;
        for(int i=n-1;i>=0;i--) sa[--cnt[s[i]]]=i ;
        for(int len=1;len<=n;len*=2)
        {
            int num=0 ;
            for(int i=n-len;i<n;i++) pri[num++]=i ;
            for(int i=0;i<n;i++) if(sa[i]>=len) pri[num++]=sa[i]-len ;
            for(int i=0;i<m;i++) cnt[i]=0 ;
            for(int i=0;i<n;i++) cnt[rank[i]]++ ;
            for(int i=1;i<m;i++) cnt[i]+=cnt[i-1] ;
            for(int i=n-1;i>=0;i--) sa[--cnt[rank[pri[i]]]]=pri[i] ;
            for(int i=0;i<n;i++) rank2[i]=rank[i] ;
            rank[sa[0]]=0 ; num=1 ;
            for(int i=1;i<n;i++) rank[sa[i]]=
                (rank2[sa[i]]==rank2[sa[i-1]] &&
                rank2[sa[i]+len]==rank2[sa[i-1]+len])
                ? num-1 : num++ ;
            if(num>=n) break ;
            m=num ;
        }
    }
 
    bool build_h=0 ;
    int log_t[maxn] , *rmq[LOG] ;
    void build_height(bool buildrmq=1)
    {
        int now=0 ;
        for(int i=0;i<n;i++)
        {
            if(now) now-- ;
            if(!rank[i]) continue ;
            while(s[ sa[rank[i]]+now ]==s[ sa[rank[i]-1]+now ]) now++ ;
            height[rank[i]]=now ;
        }
        build_h=1 ;
        if(!buildrmq) return ;
 
        log_t[0]=log_t[1]=0 ;
        for(int i=2;i<=n;i++) log_t[i]=log_t[i/2]+1 ;
        for(int i=0;(1<<i)<=n;i++) rmq[i]=new int[n+1] ;
        for(int i=0;(1<<i)<=n;i++) for(int j=0;j+(1<<i)-1<=n;j++)
            rmq[i][j]=(i ?
            min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]) :
            height[j]) ;
    }
 
    int comp_suffix(char *p,int x,int len)
    {
        return strncmp(p,s+sa[x],len) ;
    }
 
    int lower_bound(char *p,int len)
    {
        int l=0 , r=n ;
        while(r-l>1)
        {
            int mid=(r+l)/2 ;
            if(comp_suffix(p,mid,len)>0) l=mid ;
            else r=mid ;
        }
        return r ;
    }
 
    int upper_bound(char *p,int len)
    {
        int l=0 , r=n ;
        while(r-l>1)
        {
            int mid=(r+l)/2 ;
            if(comp_suffix(p,mid,len)>=0) l=mid ;
            else r=mid ;
        }
        return r ;
    }
 
    int find(char *p,int len)
    {
        return upper_bound(p,len)-lower_bound(p,len) ;
    }
 
    int LCP(int x,int y)
    {
        if(!build_h) build_height() ;
        x=rank[x] ; y=rank[y] ;
        if(x>y) swap(x,y) ;
        if(x==y) return n-sa[x]-1 ;
        x++ ;
        int t=log_t[y-x+1] ;
        return min(rmq[t][x],rmq[t][y-(1<<t)+1]) ;
    }
};
 
int num[maxn][maxn] ;
int getnum(char *s)
{
    int len=strlen(s) , ret=0 ;
    int l=SufArr::lower_bound(s,len) ;
    int r=SufArr::upper_bound(s,len) ;
    for(int i=l;i<r;i++)
    {
        int x=SufArr::sa[i] ;
        ret+=num[x][x+len-1] ;
    }
//    printf("%s : %d\n",s,ret) ;
    return ret ;
}
 
bool check(char *t)
{
//    printf("%s : ",t) ;
    int n=strlen(t) ;
    for(int i=0;n-1-i>=i;i+=2) if(t[i]!=t[n-1-i])
        return 0 ;
    return 1 ;
}
char s[maxn],ans[maxn] ;
main()
{
    int k ; scanf("%s%d",s,&k) ;
    SufArr::init(s) ;
    SufArr::build_sa() ;
    int n=strlen(s) ;
    for(int i=0;i<2*n-1;i++)
    {
        int x=i/2 , y=i-x ;
        for(int j=1;x-j+1>=0 && y+j-1<n && s[x-j+1]==s[y+j-1];j+=2)
            num[x-j+1][y+j-1]=1 ;
        for(int j=2;x-j+1>=0 && y+j-1<n && s[x-j+1]==s[y+j-1];j+=2)
            num[x-j+1][y+j-1]=1 ;
    }
    for(int i=0;i<n;i++) for(int j=n-1;j>=i;j--)
        num[i][j]+=num[i][j+1] ;
    for(int i=0,last=0;;i++)
    {
        if(k<=last){printf("%s\n",ans) ; return 0 ;}
        k-=last ;
        int num1,num2 ;
        ans[i]='a' ; num1=getnum(ans) ;
        ans[i]='b' ; num2=getnum(ans) ;
        if(k>num1) k-=num1 ;
        else ans[i]='a' ;
        last=(check(ans) ? SufArr::find(ans,i+1) : 0) ;
    }
}
 

沒有留言:

張貼留言