地址：http://acm.hdu.edu.cn/showproblem.php?pid=2072
lily的好朋友xiaoou333最近很空，他想了一件没有什么意义的事情，就是统计一篇文章里不同单词的总数。下面你的任务是帮助xiaoou333解决这个问题。
Input 有多组数据，每组一行，每组就是一篇小文章。每篇小文章都是由小写字母和空格组成，没有标点符号，遇到#时表示输入结束。 Output 每组只输出一个整数，其单独成行，该整数代表一篇文章里不同单词的总数。 Sample Input
you are my friend
#
Sample Output
4
set做法：
#include<iostream>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;
set<string>se;
int main()
{
string s;
while(getline(cin,s))
{
if(s[]=='#')
break;
string m;
se.clear();
int len=s.length();
// cout<<"len: "<<len<<endl;
for(int i=;i<len;i++)
{
// cout<<i<<" "<<s[i]<<endl;
if(s[i]>='a'&&s[i]<='z')
{
int j;
m.clear();
for(j=i;j<len&&s[j]>='a'&&s[j]<='z';j++)
{
m+=s[j];
}
i=j;
se.insert(m);
}
}
cout<<se.size()<<endl;
}
return ;
}
istringstream 做法（具体的我看不太懂，反正可以去掉空格）：
#include<iostream>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<set>
using namespace std;
typedef long long ll;
set<string>q;
int main()
{
string s;
while(getline(cin,s)){
if(s[]=='#')
break;
istringstream sss(s);
q.clear();
string ss;
while(sss>>ss){
q.insert(ss);
}
cout<<q.size()<<endl;
}
return ;
}
重点是字典树操作，由于对num数组的理解不透彻，写出了一堆BUG，自己实在不会变通啊。
这里的num数组记录的是：标记当前字符串结尾。比如qwe qw : 先是qwe可以得到： 1(q) 2(w) 3(e) 4
0 0 1
表示以e结尾的加入了
然后qw，k=2处，num=1，表示以w结尾的加入了。这就是两个单词。
上代码吧，开始看ac自动机了
#include<iostream>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;
#include<map>
const int maxn=1e4+;
int tr[maxn][];
int num[maxn];
string s;
string mid;
int k=;
int ans=;
int join()
{
int p=;
int len=mid.length();
int ok1=,ok2=;
for(int i=;i<len;i++)
{
int c=mid[i]-'a';
if(!tr[p][c])
{
tr[p][c]=k++;
}
p=tr[p][c];
}
if(!num[p]) //当前单词结尾没被标记，说明是一个新的单词。
{
num[p]=;
return ;
}
else
return ;
}
int main() //qq as a
{
while(getline(cin,s))
{
if(s[]=='#')
break;
k=;
ans=;
memset(tr,,sizeof(tr));
memset(num,,sizeof(num));
int len=s.length();
for(int i=;i<len;i++)
{
if(s[i]>='a'&&s[i]<='z')
{
mid.clear();
int j;
for(j=i;j<len&&s[j]>='a'&&s[j]<='z';j++)
{
mid+=s[j];
}
i=j;
//
if(join()==)
{
ans++;
// cout<<mid<<" "<<ans<<endl;
}
}
}
cout<<ans<<endl;
}
return ;
}