gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
Pku 3630--Phone List(Trie)
直接套用Trie
#include <stdio.h>
#include <cstring>

const int CAP = 10 ;
const int MAXN = 80001 ;


struct TREENODE
{
    TREENODE *next[CAP] ;
    bool exist ;
    TREENODE() {
        exist = false ;

        for ( int i = 0 ; i < CAP ; ++i )
            next[i] = NULL ;
    }
} ;
TREENODE g_Temp[MAXN] ;

void Del(int pos)
{
    for ( int i = 0 ; i < CAP ; ++i )
        g_Temp[pos].next[i] = NULL ;
    g_Temp[pos].exist = false ;
}

struct TRIE
{
    TREENODE *head ;
    int m_Index ;

    TRIE() {
        m_Index = 1 ;
        head = &g_Temp[0] ;
    }

    bool Insert( char* phNum )
    {
        TREENODE *ptr = head ;
        int len = strlen(phNum) ;

        for ( int i = 0 ; i < len ; ++i )
        {
            if ( ptr->next[phNum[i] - '0'] == NULL )
            {
                Del( m_Index ) ;
                ptr->next[phNum[i] - '0'] = &g_Temp[m_Index++] ;
            }
            else if ( i == len - 1 )
            {
                return true ;
            }
            else if ( ptr->next[phNum[i] - '0']->exist )
            {
                return true ;
            }
            ptr = ptr->next[phNum[i] - '0'] ;
        }
        
        ptr->exist = true ;

        return false ;
    }

    void Init()
    {
        m_Index = 1 ;
        Del( 0 ) ;
    }

} ;

int main()
{
//    freopen("in.txt", "r", stdin) ;
    int t , n , i ;
    char phoneNum[12] ;
    bool collision ;
    scanf("%d", &t) ;
    TRIE trie ;
    while ( t-- )
    {
        scanf("%d", &n) ;
        collision = false ;
        trie.Init() ;

        for ( i = 0 ; i < n ; ++i )
        {
            scanf("%s", &phoneNum) ;

            if ( !collision )
            {
                collision = trie.Insert( phoneNum ) ;
            }
        }

        if ( !collision ) {
            printf("YES\n") ;
        }
        else {
            printf("NO\n") ;
        }
    }
    return 0 ;
}
posted on 2008-11-09 23:58 巫 阅读(173) 评论(0)  编辑 收藏 引用 所属分类: 字符串处理

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