gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
Pku 2503--Babelfish
#include <stdio.h>
#include <cstring>

const int MAXN = 131101 ;
const int SIZE = 100001 ;
struct HashItem
{
    char matchStr[12] ;
    char memStr[12] ;
    HashItem *next ;
    HashItem() {
        next = NULL ;
    }
}hash[MAXN] , g_Temp[SIZE] ;

int g_Pos ;

int RKHash( char *str )
{
    unsigned long hash = 0 ;

    while ( *str )
    {
        hash = (hash * 26) + (*str - 'a') ;
        str++ ;
    }

    return (hash % MAXN) ;
}

void Insert( char *str , char *mstr )
{
    int key = RKHash( str ) ;

    HashItem *p = &g_Temp[g_Pos++] ;
    strcpy( p->memStr, mstr ) ;
    strcpy( p->matchStr, str ) ;
    p->next = NULL ;
    p->next = hash[key].next ;
    hash[key].next = p ;
    
}

int Find( char *str , char *mstr )
{
    int key = RKHash( str ) ;
    int pos = 0 ;

    HashItem *p = hash[key].next ;

    while ( p )
    {
        if ( strcmp( p->matchStr, str ) == 0 )
        {
            pos = 1 ;
            strcpy( mstr, p->memStr ) ;
            break ;
        }
        p = p->next ;
    }
    
    return pos ;
}

void Init()
{
    g_Pos = 0 ;

    for ( int i = 0 ; i < MAXN ; ++i )
        hash[i].next = NULL ;
}

int main()
{
    char str[2][12] , tmpStr[50] ;
    int x ;

    Init() ;

    while ( gets(tmpStr) && tmpStr[0] )
    {
        sscanf( tmpStr, "%s%s", str[0], str[1] ) ;

        Insert( str[1], str[0] ) ;
    }

    while ( scanf("%s", &str[0]) != EOF )
    {
        x = Find( str[0] , str[1] ) ;

        if ( x == 1 )
        {
            printf("%s\n", str[1]) ;
        }
        else {
            printf("eh\n") ;
        }
    }

    return 0 ;
}
posted on 2008-11-09 23:15 巫 阅读(404) 评论(0)  编辑 收藏 引用 所属分类: Hash应用

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