链表：

http://acm.hdu.edu.cn/showproblem.php?pid=1075

题目:

What Are You Talking About

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 102400/204800 K (Java/Others)
Total Submission(s): 7939    Accepted Submission(s): 2470

START
from fiwo
hello difh
mars riwosf
earth fnnvk
like fiiwj
END
START
difh, i'm fiwo riwosf.
i fiiwj fnnvk!
END

hello, i'm from mars.
i like earth!

分析与总结：

弱逼第一次写字典树 = =|| ， 找了几分资料研究了后，自己敲起来， 结果因为数组开太小WA了，改了大了之后就科学地AC了。

先写了一个动态分配内存版本，用C++提交，用了250MS。

然后又写了一个静态内存开辟的版本， 用了187MS，  看来静态的确实比较快。

代码：

1. 动态分配内存版

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;

const int KIND = 26;

struct node{
    int  pos;
    bool isword;
    node *next[KIND];
    node(){
        isword=false;
        memset(next, 0, sizeof(next));
    }
};

void insert(node *root, char *str, int pos){
    for(char *p=str; *p; ++p){
        int son = *p-'a';
        if(root->next[son]==NULL){
            root->next[son] = new node;
        }
        root = root->next[son];
    }
    root->isword = true;
    root->pos    = pos;
}
int search(node *root, char *str){
    for(char *p=str; *p; ++p){
        int son = *p-'a';
        if(root->next[son]==NULL)
            return -1;
        root = root->next[son];
    }
    if(root->isword)return root->pos;
    return -1;
}

char word[500010][12];
int pos;

int main(){ 
    char str[3005], str2[3005];
    pos=0;
    gets(str);
    node *root = new node;
    while(scanf("%s %s",str,str2)){
        if(str[0]=='E')break;
        strcpy(word[pos], str);
        insert(root, str2, pos++); 
    }
    gets(str);
    while(gets(str)){
        if(str[0]=='E')break;
        bool flag=false;
        int k=0;
        for(char *p=str; *p; ++p){
            if(!flag&&!isalpha(*p)){
                printf("%c",*p);
            }
            else if(flag && !isalpha(*p)){
                flag=false;
                int t=search(root, str2);
                if(t==-1) printf("%s%c",str2,*p);
                else printf("%s%c",word[t],*p);
            }
            else if(flag){
                str2[k++]=*p;
            }
            else if(!flag&&isalpha(*p)){
                flag=true;
                k=0; 
                memset(str2, 0, sizeof(str2));
                str2[k++]=*p;
            }
        } 
        puts("");
    }
    return 0;
}

2. 静态开辟内存空间版

用了个小技巧， 单独写了一个"new node"的newNode()函数，这样只需要把上面代码分配空间部分都改为用这个函数代替就OK了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;

const int KIND = 26;

struct node{
    int  pos;
    bool isword;
    node *next[KIND];
    void init(){
        isword=false;
        memset(next, 0, sizeof(next));
    }
}arr[1000000];
int cntNode;

inline node* newNode(){
    arr[cntNode].init();
    return &arr[cntNode++];
}

void insert(node *root, char *str, int pos){
    for(char *p=str; *p; ++p){
        int son = *p-'a';
        if(root->next[son]==NULL){
            root->next[son] = newNode();
        }
        root = root->next[son];
    }
    root->isword = true;
    root->pos    = pos;
}
int search(node *root, char *str){
    for(char *p=str; *p; ++p){
        int son = *p-'a';
        if(root->next[son]==NULL)
            return -1;
        root = root->next[son];
    }
    if(root->isword)return root->pos;
    return -1;
}

char word[500010][12];
int pos;

int main(){ 
    char str[3005], str2[3005];
    pos=0;
    cntNode=0;

    gets(str);
    node *root = newNode();

    while(scanf("%s %s",str,str2)){
        if(str[0]=='E')break;
        strcpy(word[pos], str);
        insert(root, str2, pos++); 
    }
    gets(str);
    while(gets(str)){
        if(str[0]=='E')break;
        bool flag=false;
        int k=0;
        for(char *p=str; *p; ++p){
            if(!flag&&!isalpha(*p)){
                printf("%c",*p);
            }
            else if(flag && !isalpha(*p)){
                flag=false;
                int t=search(root, str2);
                if(t==-1) printf("%s%c",str2,*p);
                else printf("%s%c",word[t],*p);
            }
            else if(flag){
                str2[k++]=*p;
            }
            else if(!flag&&isalpha(*p)){
                flag=true;
                k=0; 
                memset(str2, 0, sizeof(str2));
                str2[k++]=*p;
            }
        } 
        puts("");
    }
    return 0;
}

——  生命的意义，在于赋予它意义。
          
     原创 http://blog.csdn.net/shuangde800 ， By   D_Double  (转载请标明)