Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 66022    Accepted Submission(s): 16607

Problem Description

lily的好朋友xiaoou333最近很空，他想了一件没有什么意义的事情，就是统计一篇文章里不同单词的总数。下面你的任务是帮助xiaoou333解决这个问题。

 

 

Input

有多组数据，每组一行，每组就是一篇小文章。每篇小文章都是由小写字母和空格组成，没有标点符号，遇到#时表示输入结束。

 

 

Output

每组只输出一个整数，其单独成行，该整数代表一篇文章里不同单词的总数。

 

 

Sample Input

you are my friend #

 

 

Sample Output

4

 

 

Author

Lily

 

 

Source

 

 

Recommend

linle   |   We have carefully selected several similar problems for you:            

 

 

本来想直接map，但是测试了一下单词可能很长，map就不适用了，所以用字典树，每次输入一行，也就是样例的间隔是回车，样例内部单词的间隔是空格，所以用getline读入一个string，然后用istringstream，一次读入一个单词，ex标记单词是否存在。

代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;int pos;int trie[100001][26];bool ex[100001];int Insert(string s) {    int i = 0,c = 0,len = s.size();    while(i < len) {        int d = s[i] - 'a';        if(!trie[c][d]) {            trie[c][d] = ++ pos;        }        c = trie[c][d];        i ++;    }    if(!ex[c]) {        ex[c] = true;        return 1;    }    return 0;}int main() {    string s;    while(getline(cin,s) && s != "#") {        istringstream in(s);        memset(ex,false,sizeof(ex));        string t;        int c = 0;        while(in>>t) {            c += Insert(t);        }        printf("%d\n",c);    }}