gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
Pku 2774--Long Long Message（后缀数组）
Memory: 4440K Time: 657MS
Language: C++ Result: Accepted
#include <stdio.h>
#include <cstring>

const int MAX = 201000 ;

int n ;

int cnt[MAX] , array[4][MAX] , *rank , *nrank , *sa , *nsa , h[MAX] ;
char SText[MAX] ;

void CreateSuffix()
{
    int i , k ;
    rank = array[0] ;
    nrank = array[1] ;
    sa = array[2] ;
    nsa = array[3] ;

    for ( i = 0 ; i < n ; i++ )
    {
        cnt[SText[i]]++ ;
    }
    for ( i = 1 ; i < 256 ; i++ )
    {
        cnt[i] += cnt[i - 1] ;
    }
    for ( i = n - 1 ; i >= 0 ; i-- )
    {
        sa[--cnt[SText[i]]] = i ;
    }
    for ( rank[sa[0]] = 0 , i = 1 ; i < n ; i++ )
    {
        rank[sa[i]] = rank[sa[i - 1]] ;
        if ( SText[sa[i]] != SText[sa[i - 1]] )
        {
            rank[sa[i]]++ ;
        }
    }

    for ( k = 1 ; k < n && rank[sa[n - 1]] < n - 1; k *= 2 )
    {
        for ( i = 0 ; i < n ; i++ )
            cnt[rank[sa[i]]] = i + 1 ;
        for ( i = n - 1 ; i >= 0 ; i-- )
        {
            if ( sa[i] - k >= 0 )
            {
                nsa[--cnt[rank[sa[i] - k]]] = sa[i] - k ;
            }
        }

        for ( i = n - k ; i < n ; i++ )
        {
            nsa[--cnt[rank[i]]] = i ;
        }

        for ( nrank[nsa[0]] = 0 , i = 1 ; i < n ; i++ )
        {
            nrank[nsa[i]] = nrank[nsa[i - 1]] ;
            if ( rank[nsa[i]] != rank[nsa[i - 1]]
                || rank[nsa[i] + k] != rank[nsa[i - 1] + k] )
            {
                nrank[nsa[i]]++ ;
            }
        }

        int *t = rank ; rank = nrank ; nrank = t ;
        t = sa ; sa = nsa ; nsa = t ;
    }
}

void CalHeight()
{
    int i , j , k ;
    for ( i = 0 , k = 0 ; i < n ; i++ )
    {
        if ( rank[i] == n - 1 )
            h[rank[i]] = k = 0 ;
        else {
            if ( k > 0 ) k-- ;
            j = sa[rank[i] + 1] ;
            for ( ; SText[i + k] == SText[j + k] ; k++ ) ;
            h[rank[i]] = k ;
        }
    }
}

int main()
{
    char ks[MAX] ;
    int i , j , k , len , p1 , p2 , ans = 0 ;

    //scanf("%s", &SText) ;
    gets(SText) ;
    gets(ks) ;
    //scanf("%s", &ks ) ;

    len = strlen(SText) ;
    SText[len] = '#' ;

    strcat( SText , ks ) ;

    n = strlen ( SText ) ;
    SText[n++] = 0 ;
    memset(cnt, 0, sizeof(cnt)) ;

    CreateSuffix() ;
    CalHeight() ;

    for ( i = 0 ; i < n - 1 ; i++ )
    {
        j = sa[i]; 
        if(j < len)p1 = 1; 
        else p1 = -1; 
        
        k = sa[i+1]; 
        if(k < len)p2 = 1; 
        else p2 = -1; 
        
        if(p1*p2<1 && h[i]>ans) 
            ans = h[i]; 
    }

    printf("%d\n", ans) ;
    
    return 0 ;
}
posted on 2008-11-08 14:17 巫 阅读(571) 评论(0)  编辑 收藏 引用 所属分类: 字符串处理

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理