gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
直接套用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 阅读(175) 评论(0)  编辑 收藏 引用 所属分类: 字符串处理

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