gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
Pku 2774--Long Long Message（后缀树）
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 *r = 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 , *r = 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, 0, 0, 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 巫 阅读(587) 评论(1)  编辑 收藏 引用 所属分类: 字符串处理

评论

# re: Pku 2774--Long Long Message（后缀树） 2011-05-15 13:51 dereky
求教大牛，那个Lt属性是记录什么的  回复  更多评论
  


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