精品免费久久久久久久,亚洲国产成人久久一区久久,久久国产精品免费

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 巫閱讀(583) 評論(0) 編輯收藏引用所屬分類: 字符串處理

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: POJ 2408--Anagram Groups Pku 3080--Blue Jeans(暴力枚舉 + KMP) Pku 3630--Phone List(Trie) Pku 2503--Babelfish(Trie) Pku 1816--Wild Words(Trie + DFS) Pku 2513--Colored Sticks（Trie） Pku 2774--Long Long Message（后綴數組） Pku 2774--Long Long Message（后綴樹）

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

gzwzm06

常用鏈接

留言簿(3)

隨筆檔案

文章分類

文章檔案

搜索

最新評論