比赛 20160407树结构练习 评测结果 AAAAAAAAAA
题目名称 单词查找树 最终得分 100
用户昵称 haah 运行时间 0.016 s
代码语言 C++ 内存使用 3.98 MiB
提交时间 2016-04-07 19:49:52
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<map>
using namespace std;
char line[100];
struct letter{
    char d;
    int son,bro;
}tr[320000];
int tot;
void insert(char s[]){
    int len=strlen(line);
    int now=0;
    for(int i=0;i<len;i++){
        if(tr[now].son==0){
            tr[++tot].d=s[i];
            tr[now].son=tot;
            now=tot;
        }
        else{
            now=tr[now].son;
            while(tr[now].d!=s[i]&&tr[now].bro>0){
                now=tr[now].bro;
            }
            if(tr[now].d!=s[i]){
                tr[++tot].d=s[i];
                tr[now].bro=tot;
                now=tot;
            }
        }
    }
}
int main(){
    freopen("trie.in","r",stdin);
    freopen("trie.out","w",stdout);
    while(scanf("%s",line)!=EOF){
        insert(line);
    }
    printf("%d",tot+1);
    return 0;
}