程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> foj 2075 Substring

foj 2075 Substring

編輯:C++入門知識

題目大意:求恰好出現n次的字典序最小的串。

題目思路:後綴數組加單調棧,n為1的時候要特判,不過數據有點水,不判都能過。

[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 100010 
int max(int a,int b) 

    return a>b?a:b; 

int min(int a,int b) 

    return a<b?a:b; 

int height[M],rank[M],r[M],sa[M]; 
int ts[M],ta[M],tb[M],tv[M],pos,st,ed; 
struct node 

    int h,st,w; 
}q[M]; 
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 m) 

    int i,j,*x=ta,*y=tb,p; 
    for(i=0;i<m;i++) ts[i]=0; 
    for(i=0;i<n;i++) ts[x[i]=r[i]]++; 
    for(i=1;i<m;i++) ts[i]+=ts[i-1]; 
    for(i=n-1;i>=0;i--) sa[--ts[x[i]]]=i; 
 
    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); 
        x[sa[0]]=0; 
        p=1; 
        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,tmp; 
    for(i=1;i<=n;i++) rank[sa[i]]=i; 
    k=0; 
    for(i=0;i<n;i++) 
    { 
        tmp=sa[rank[i]-1]; 
        for(;r[i+k]==r[tmp+k];k++) 
        ; 
        height[rank[i]]=k; 
        k?--k:0; 
    } 

char s[M]; 
int  solve(int len,int k) 

    int i; 
    node tmp; 
    int top=0,tail=0; 
    height[len+1]=0; 
    if(k==1) 
    { 
        st=0,ed=len; 
        return 1; 
    } 
    for(i=1;i<=len+1;i++) 
    { 
        tmp.h=0; 
        tmp.st=i; 
        while(top<tail&&q[tail-1].w>=height[i]) 
        { 
            tmp.h+=q[tail-1].h; 
            tmp.st=q[tail-1].st; 
            tmp.w=q[tail-1].w; 
            if(tmp.h==k-1&&tmp.w>height[i]) 
            { 
                st=sa[tmp.st]; 
                if(top<tail-1) 
                    ed=st+max(height[i]+1,q[tail-2].w+1); 
                else 
                    ed=st+height[i]+1; 
                return 1; 
            } 
            tail--; 
        } 
        if(height[i]==0) 
            continue; 
        tmp.w=height[i]; 
        tmp.h+=1; 
        q[tail++]=tmp; 
    } 
    return 0; 

int main() 

    int i,k,len; 
    while(scanf("%d",&k)!=EOF) 
    { 
        scanf("%s",s); 
        len=strlen(s); 
        for(i=0;i<len;i++) 
            r[i]=s[i]+1; 
        r[len]=0; 
        da(len+1,200); 
        calh(len); 
        if( solve(len,k)==0) 
        { 
            puts("impossible"); 
            continue; 
        } 
        for(i=st;i<ed;i++) 
            printf("%c",s[i]); 
        puts(""); 
    } 


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved