gzwzm06

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks

<

2025年11月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

常用鏈接

留言簿(3)

隨筆檔案

2009年5月 (1)

文章分類

文章檔案

搜索

最新評論

1.?re: Pku 2774--Long Long Message（后綴樹）
求教大牛，那個Lt屬性是記錄什么的
--dereky
2.?re: POJ 2481(樹狀數組)
@gzwzm06
哦，實在是不好意思，確實是那個地方，現在過了，謝謝了啊。
--Klion
3.?re: POJ 2481(樹狀數組)
你再檢查下，cc[j].m_e == cc[j].m_e這個條件肯定是真的，沒有意義吧
--gzwzm06
4.?re: POJ 2481(樹狀數組)
@gzwzm06
兩個相同一起比較也就是兩個區間是一樣的，起點和終點是相同的，和您的第80行比較的應該是一樣的吧？
--Klion
5.?re: POJ 2481(樹狀數組)
評論內容較長,點擊標題查看
--gzwzm06

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

只有注冊用戶登錄后才能發表評論。


相關文章: 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 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品