题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2072
单词数
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 77401 Accepted Submission(s): 19552
Problem Description
lily的好朋友xiaoou333最近很空,他想了一件没有什么意义的事情,就是统计一篇文章里不同单词的总数。下面你的任务是帮助xiaoou333解决这个问题。
Input
有多组数据,每组一行,每组就是一篇小文章。每篇小文章都是由小写字母和空格组成,没有标点符号,遇到#时表示输入结束。
Output
每组只输出一个整数,其单独成行,该整数代表一篇文章里不同单词的总数。
Sample Input
you are my friend #
Sample Output
4
解题思路:
(水题)建立字典树,对于单词节点,只统计一次,总的单词节点数目即为答案
(;´༎ຶД༎ຶ`)这道题数组开到1E4就能过。。不然MLE枯了
ac代码:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#include <fstream>
typedef long long ll;
const int maxn=1e4;
using namespace std;
int tot=0,ans=0;//总节点数
int tree[maxn][30],vis[maxn];
string s,s1;
void build(string s)
{
int root=0,len=s.length();
for(int i=0;i<len;i++)
{
int id=s[i]-'a';
if(!tree[root][id]) tree[root][id]=++tot;//建新的节点
root=tree[root][id];
}
if(!vis[root])//单词节点只访问一次
{
vis[root]=1;
ans++;
}
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
while(getline(cin,s))
{
memset(tree,0,sizeof(tree));
memset(vis,0,sizeof(vis));
ans=0;
if(s[0]!='#')
{
stringstream ss(s);
while(ss>>s1)
build(s1);
printf("%d\n",ans);
ss.clear();
}
}
return 0;
}