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

gzwzm06

  C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
  1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks
Memory: 74320K Time: 797MS
Language: C++ Result: Accepted
#include <stdio.h>
#include 
<string>
using namespace std ;

const int MAXN = 200000 ;
const int APSIZE = 30 ;

struct SuffixTreeNode
{
    SuffixTreeNode 
*descendants[APSIZE] ;
    
int m_left[APSIZE], m_right[APSIZE] ;
    SuffixTreeNode 
*suffixLink ;

    SuffixTreeNode()
    
{
        
for ( int i = 0 ; i < APSIZE ; ++i )
        
{
            m_left[i] 
= -1 ;
        }

    }

}
 ;

SuffixTreeNode g_STNode[MAXN] ;
int g_Level = 0 ;

SuffixTreeNode
* NewSuffixTreeNode()
{
    SuffixTreeNode 
*ptr = &g_STNode[g_Level++] ;

    
return ptr ;
}


SuffixTreeNode 
*root ;
        
struct UkkonenSuffixTree
{
    
    
int offset ;
    
int Lt ;

    
string T ;

    
bool endPoint ;

    UkkonenSuffixTree(
int from)
    
{
        Lt 
= 1 ;
        offset 
= from ;
    }

    
    SuffixTreeNode
* TestAndSplit( SuffixTreeNode *p, int i )
    
{
        
int Rt = i - 1 ;
        
if ( Lt <= Rt )
        
{
            
int pos = T.at(Lt) - offset ;
            SuffixTreeNode
* pp = p->descendants[pos] ;
            
int lt = p->m_left[pos] ;
            
int rt = p->m_right[pos] ;

            
if ( T.at(i) == T.at( lt + Rt - Lt + 1 ) )
            
{
                endPoint 
= true ;
                
return p ;
            }

            
else {
                pos 
= T.at(lt) - offset ;
                SuffixTreeNode 
*= p->descendants[pos] = NewSuffixTreeNode() ;
                p
->m_right[pos] = lt + Rt - Lt ;
                pos 
= T.at(lt + Rt - Lt + 1- offset ;
                r
->descendants[pos] = pp ;
                r
->m_left[pos] = lt + Rt - Lt + 1 ;
                r
->m_right[pos] = rt ;
                endPoint 
= false ;
                
return r ;
            }

        }

        
else if ( p->m_left[T.at(i) - offset] == -1 )
        
{
            endPoint 
= false ;
        }

        
else
            endPoint 
= true ;
        
return p ;
    }


    SuffixTreeNode
* FindCanonicalNode( SuffixTreeNode *p, int Rt )
    
{
        
if ( Rt >= Lt )
        
{
            
int pos = T.at(Lt) - offset ;
            SuffixTreeNode 
*pp = p->descendants[pos] ;
            
int lt = p->m_left[pos] ;
            
int rt = p->m_right[pos] ;
            
while ( rt - lt <= Rt - Lt )
            
{
                Lt 
= Lt + rt - lt + 1;
                p 
= pp ;
                
if ( Lt <= Rt )
                
{
                    pos 
= T.at(Lt) - offset ;
                    pp 
= p->descendants[pos] ;
                    lt 
= p->m_left[pos] ;
                    rt 
= p->m_right[pos] ;
                    
if ( p == root )
                        pp 
= root ;
                }

            }

        }


        
return p ;
    }


    SuffixTreeNode
* Update( SuffixTreeNode *p, int i )
    
{
        SuffixTreeNode 
*prev = NULL , *= TestAndSplit( p, i ) ;

        
while ( !endPoint )
        
{
            
int pos = T.at(i) - offset ;
            r
->m_left[pos] = i ;
            r
->m_right[pos] = T.length() - 1 ;

            
if ( prev != NULL )
                prev
->suffixLink = r ;
            prev 
= r ;

            
if ( p == root )
                Lt
++ ;
            
else
                p 
= p->suffixLink ;

            p 
= FindCanonicalNode( p, i - 1 ) ;
            r 
= TestAndSplit( p, i ) ;

        }


        
if ( prev != NULL )
            prev
->suffixLink = p ;
        
return p ;
    }


    
void Run( string text )
    
{
        T 
= text ;
        
int n = T.length() , pos = T.at(0- offset ;

        root 
= NewSuffixTreeNode() ;
        root
->suffixLink = root ;
        
        root
->m_left[pos] = 0 ;
        root
->m_right[pos] = n - 1 ;
        
        SuffixTreeNode 
*canonicalNodeAP = root , *canonicalNodeEP ;
        
for ( int i = 1 ; i < n ; ++i )
        
{
            canonicalNodeEP 
= Update( canonicalNodeAP, i ) ;
            canonicalNodeAP 
= FindCanonicalNode( canonicalNodeEP, i ) ;
        }

    }


}
 ;

int length = 0 , s1length = 0 ;
void TraverseTree(SuffixTreeNode *p, int lt, int len, bool& a, bool& b )
{
    
bool edge1 = false, edge2 = false ;

    
for ( int i = 0 ; i < APSIZE ; ++i )
    
{
        
if ( p->m_left[i] != -1 )
        
{
            
if ( p->descendants[i] == NULL )
            
{
                
if ( p->m_left[i] <= s1length )
                    a 
= edge1 = true ;
                
else
                    b 
= edge2 = true ;
            }

            
else {
                TraverseTree( p
->descendants[i], p->m_left[i],
                    len 
+ (p->m_right[i] - p->m_left[i] + 1) , edge1, edge2 ) ;

                
if ( edge1 )
                    a 
= true ;
                
if ( edge2 )
                    b 
= true ;
            }

            
if ( edge1 && edge2 && len > length )
            
{
                length 
= len ;
            }

        }

    }

}


int FindLongest()
{
    
bool edge1 = false , edge2 = false ;

    TraverseTree( root, 
00, edge1, edge2 ) ;

    
return length ;
}



int main()
{
    
char s1[100000], s2[100000] ;
    gets(s1) ;
    gets(s2) ;
    
int l1 = strlen(s1), l2 = strlen(s2) ;
    s1[l1] 
= '|', s1[l1 + 1= '\0' ;
    s2[l2] 
= '}', s2[l2 + 1= '\0' ;
    
    strcat( s1, s2 ) ;

    s1length 
= l1 ;;
    UkkonenSuffixTree t(
'a') ;
    t.Run(s1) ;

    
int ans = FindLongest() ;

    printf(
"%d\n", ans) ;

    
return 0 ;
}
posted on 2008-11-08 14:15 閱讀(614) 評論(1)  編輯 收藏 引用 所屬分類: 字符串處理

評論

# re: Pku 2774--Long Long Message(后綴樹) 2011-05-15 13:51 dereky
求教大牛,那個Lt屬性是記錄什么的  回復  更多評論
  

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            麻豆精品视频在线| 性伦欧美刺激片在线观看| 欧美日韩国产影片| 欧美国产日韩一区二区在线观看| 欧美一区二区三区婷婷月色 | 国产性做久久久久久| 国产精品美女久久久浪潮软件| 国产精品日韩欧美| 欧美激情bt| 在线免费观看日本欧美| 国产午夜精品视频免费不卡69堂| 欧美日韩一级片在线观看| 国产精品日韩欧美一区| 国产亚洲欧美日韩日本| 亚洲国产美女| 欧美一级久久久| 亚洲国产精品一区| 亚洲网友自拍| 久久久91精品国产| 欧美久久久久久久久| 国产美女搞久久| 亚洲精品综合精品自拍| 久久国产精品毛片| 亚洲精品国产精品久久清纯直播| 香蕉久久一区二区不卡无毒影院| 你懂的亚洲视频| 国产一区二区三区四区老人| 国产精品99久久不卡二区| 免费欧美网站| 午夜精品亚洲一区二区三区嫩草| 欧美成人嫩草网站| 国产真实久久| 欧美在线高清视频| 一区二区国产在线观看| 欧美顶级大胆免费视频| 在线观看欧美日本| 久久视频在线看| 亚洲欧美日韩国产综合在线 | 亚洲一区二区视频在线观看| 麻豆亚洲精品| 国产一区视频观看| 亚洲欧美经典视频| 亚洲第一福利社区| 久久先锋影音av| 狠狠综合久久av一区二区小说| 欧美一区二区三区在线观看| 在线视频亚洲一区| 欧美视频四区| 亚洲线精品一区二区三区八戒| 91久久久久久| 欧美精品一卡二卡| 99精品视频免费观看| 欧美激情精品| 久热国产精品视频| 在线观看视频欧美| 欧美精选在线| 欧美黄色一区二区| 国产主播一区二区三区| 亚洲一区二区精品视频| 亚洲高清一区二| 免费视频最近日韩| 亚洲三级视频在线观看| 亚洲高清激情| 欧美精品久久久久久久久老牛影院 | 亚洲精品美女在线观看播放| 久久亚洲视频| 蜜臀av性久久久久蜜臀aⅴ四虎| 在线日韩中文字幕| 欧美激情一区二区三区在线视频| 中文日韩欧美| 91久久久在线| 欧美日韩精品一区| 午夜精品国产更新| 一区二区三区精密机械公司| 国产精品午夜av在线| 久久久久网站| 欧美电影在线播放| 亚洲小少妇裸体bbw| 亚洲欧美日韩国产综合| 在线观看日韩国产| 日韩一级免费| 国产一区二区三区成人欧美日韩在线观看| 久久精品国产成人| 嫩草国产精品入口| 亚洲一区二区成人| 亚洲欧美中文在线视频| 亚洲国产乱码最新视频| 99精品国产在热久久下载| 国产午夜精品视频| 亚洲精品久久久久久久久久久久 | 国产精品夫妻自拍| 久久久久综合一区二区三区| 欧美电影在线播放| 久久riav二区三区| 免费亚洲一区二区| 欧美影院在线播放| 欧美国产精品专区| 久久国产夜色精品鲁鲁99| 欧美freesex8一10精品| 欧美一二三区精品| 欧美日韩另类字幕中文| 久久天天躁狠狠躁夜夜爽蜜月| 欧美精品日韩精品| 久久青草久久| 国产精品久久久一区麻豆最新章节| 久久在线视频| 国产精品白丝黑袜喷水久久久| 久久综合色婷婷| 国产精品欧美经典| 亚洲人成网站影音先锋播放| 国产欧美一区在线| 亚洲美女电影在线| 亚洲国产精品传媒在线观看| 亚洲欧美激情一区二区| 中国女人久久久| 久久影院午夜论| 亚洲天堂成人| a91a精品视频在线观看| 久久久久高清| 欧美在线亚洲在线| 欧美视频一区在线| 亚洲人成免费| 亚洲剧情一区二区| 欧美成人精品在线播放| 欧美sm视频| 亚洲国产精品成人| 女同性一区二区三区人了人一| 久久综合狠狠综合久久激情| 国产日韩欧美高清免费| 亚洲一区二区在线免费观看视频| 一本到高清视频免费精品| 欧美成人一品| 久久一区亚洲| 香蕉久久久久久久av网站| 亚洲男人的天堂在线aⅴ视频| 欧美日韩成人在线视频| 亚洲精品视频在线播放| 亚洲精品日韩精品| 欧美超级免费视 在线| 亚洲电影下载| 在线视频精品一区| 欧美三区不卡| 亚洲欧美激情诱惑| 久久野战av| 亚洲激情第一区| 欧美女人交a| 亚洲图片在区色| 久久日韩粉嫩一区二区三区| 亚洲国产一区二区三区在线播| 欧美sm视频| 一区二区精品在线| 久久精品首页| 亚洲欧洲精品一区二区三区不卡| 欧美国产视频在线| 在线视频免费在线观看一区二区| 香蕉久久国产| 黄网站免费久久| 欧美激情视频一区二区三区在线播放 | 久久成人国产| 激情久久综艺| 久久一区免费| av成人免费在线观看| 亚洲欧美资源在线| 影音先锋欧美精品| 欧美日韩一区二区三区免费看| 一区二区欧美在线观看| 欧美一区二区三区在线观看| 影音欧美亚洲| 欧美日韩在线另类| 久久精品国产99国产精品| 欧美激情一区二区久久久| 亚洲视频久久| 激情久久综合| 国产精品视频你懂的| 老司机凹凸av亚洲导航| 中文无字幕一区二区三区| 免费一级欧美在线大片| 亚洲一区成人| 亚洲人成在线播放网站岛国| 国产精品丝袜久久久久久app| 久久久青草青青国产亚洲免观| 日韩视频中文字幕| 久久免费精品视频| 亚洲精品免费一二三区| 欧美国产日韩一二三区| 午夜精品久久久| 亚洲国产一成人久久精品| 国产日韩欧美在线看| 欧美日韩国产一级片| 久久视频一区| 欧美一区精品| 亚洲一区视频在线| 亚洲精品国产视频| 免费观看亚洲视频大全| 欧美伊人久久| 亚洲一区二区三区视频播放| 亚洲国产成人在线播放| 国产亚洲毛片在线| 国产精品自在线| 欧美日韩亚洲激情|