gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
Pku 2503--Babelfish(Trie)

 

#include <stdio.h>
#include <cstring>

#define CAP 26
typedef struct NODE
{    
    NODE()
    {
        cnt = 0;
        id = 0;
        memset(next, NULL, sizeof(NODE));
    };
    NODE *next[CAP];
    int cnt;
    int id;
}NODE;

const int MEMORY = 150001 ;

NODE memory[MEMORY] ;
class BTree
{
public:
    BTree()
    {
        index = 1;
        id_index = 0;
        head = &memory[0];
    }

    //插入单词（返回单词ID）
    int insert(char *str)
    {
        int len = (int)strlen(str);
        NODE *pt = head;
        for (int i = 0; i < len; ++i)
        {
            if (pt->next[str[i]-'a'] == NULL)
            {
                pt->next[str[i]-'a'] = &memory[index++];
            }
            
            pt = pt->next[str[i]-'a'];
        }

        (pt->cnt)++;//单词累加一
        
        return pt->id;
    }

    //查找单词（返回单词个数）
    int find(char *str, int &pos )
    {
        int len = (int)strlen(str);
        NODE *pt = head;
        for (int i = 0; i < len; ++i)
        {
            if (pt->next[str[i]-'a'] == NULL)
            {
                return 0;
            }
            
            pt = pt->next[str[i]-'a'];
        }
        pos = pt->id ;
        
        return pt->cnt ;
    }

public:
    NODE *head;
    int id_index;    //单词ID索引
};


int main()
{
    BTree tire ;
    char str[2][12] , dict[100001][12] , tmp ;
    int state = 0 , wh = 0 , pos = 0 , x ;

    while ( true )
    {
        tmp = getchar() ;
        if ( state == 0 && tmp == '\n' )
            break ;
        if ( state == 0 )
        {
            if ( tmp == ' ' )
            {
                str[wh][pos] = 0 ;
                pos = 0 ;
                state = 1 ;
                wh = 1 ;
                continue ;
            }
            str[wh][pos++] = tmp ;
        }
        if ( state == 1 )
        {
            if ( tmp == '\n' )
            {
                str[wh][pos] = 0 ;
                x = tire.insert( str[wh] ) ;
                strcpy( dict[x], str[0] ) ;
                pos = 0 ;
                state = 0 ;
                wh = 0 ;
                continue ;
            }
            str[wh][pos++] = tmp ;
        }
    }

    while ( scanf("%s", &str[0]) != EOF )
    {
        x = tire.find( str[0] , pos ) ;

        if ( x != 0 )
        {
            printf("%s\n", dict[pos]) ;
        }
        else {
            printf("eh\n") ;
        }
    }

    return 0 ;
}
posted on 2008-11-09 22:18 巫 阅读(240) 评论(0)  编辑 收藏 引用 所属分类: 字符串处理

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