极度 YM....自己用trie写了个伪 map....( HDU 1075 )

时间：2010-08-25 来源：MiYu

MiYu原创, 转帖请注明 : 转载自 ______________白白の屋

这几天一直很YM..... 纠结.....  做个水题 1075......WA N次.....YM.
(  很简单的一题,  检索输入的串是否存在, 存在就替换输出, 不存在直接输出就可以了 )
最后无奈, 纯C++ STL..过了, 时间竟然用了 1600+MS 还是 C++交的,  G++要3400+MS,  不
明白为什么时间差那么多,  用trie 做了次, 250MS... 改了好几次效率都上不来   ....  YM 中把trie 写成了伪 map ,只有一点简单的功能,
其他的不想写了.  写得好复杂....................
伪 map 代码如下 :  好长..................... /* MiYu原创, 转帖请注明 : 转载自 ______________白白の屋    http://www.cnblog.com/MiYu Author By : MiYu Test : 4 Program : 1075 */
#include <iostream> #include <string> using namespace std; typedef struct dict DIC; DIC *root = NULL; string ext = ""; struct dict {    dict (){ str = "";memset ( child , 0 , sizeof ( child ) ); }    ~dict () { }    void del ( DIC * node );    string & insert ( char *ins,char *key = NULL );    string & find ( char *ins );    string & operator [] ( char *a );    string & operator = ( char *a );    DIC *child[26];    string str; }; void dict::del ( DIC * node ) {    if ( node == NULL ) return;    for ( int i = 0; i != 26; ++ i )    {    if ( node->child[i] != NULL ) del ( node->child[i] );    }    node->str = "";    free ( node ); } string & dict::operator [] ( char *a ) {    string &str = find ( a );    if ( str == "" )    return insert ( a );    return str; } string & dict::operator = ( char *a ) {    return this->str = a; } string & dict::insert ( char *ins,char *key ) {    DIC *cur = this,*now;    int len = strlen ( ins );    for ( int i = 0; i != len; ++ i )    {    if ( cur->child[ ins[i] - 'a' ] != NULL )    {    cur = cur->child[ ins[i] - 'a' ];    }    else    {    now = new DIC;    cur->child[ ins[i] - 'a' ] = now;    cur = now;    }    }    return cur->str; } string & dict::find ( char *ins ) {    DIC *cur = this;    int len = strlen ( ins );    for ( int i = 0; i != len; ++ i )    {    if ( cur->child[ ins[i] - 'a' ] != NULL )    cur = cur->child[ ins[i] - 'a' ];    else    return ext;    }    return cur->str; } char words[3010],temp[12],t[12]; int main () {    DIC dict;    root = &dict;    scanf ( "%s", t );    while ( scanf ( "%s", t ), strcmp ( t, "END" ) != 0 )    {    scanf ( "%s", temp );    dict[temp] = t;    }    scanf ( "%s", t );    getchar();    while ( gets ( words ) && strcmp ( words, "END" ) != 0 )    {    memset ( temp, 0, sizeof ( temp ) );    int len = strlen ( words );    for ( int i = 0,j = 0; i != len; ++ i )    {    if ( isalpha ( words[i] ) )    {    temp[j++] = words[i];    }    else    {    temp[j] = '\0';    string str = dict[ temp ];    if ( str == "" )    printf ( "%s",temp );    else    printf ( "%s",str.c_str() );    putchar ( words[i] );    j = 0;    }    }    putchar ( 10 );    }    return 0; }

STL 代码如下 : 好短....