首页 > 代码库 > HDU 2072 单词数

HDU 2072 单词数

2024-07-07 12:05:10   222人阅读

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

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

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

Sample Input
you are my friend
#
 

Sample Output
4
 
用C++的知识貌似可以很简单的解决问题，数据量不大，一行大概也就80个字符左右。 最近学习字典树，想练习一下。

思路就是建树，建树的过程中计算不同单词的数量，即判断一下这个单词插入完成后val值是否已经存在，若为正，说明该单词已经存在，若为0 ，说明该单词第一次出现。

#include<stdio.h>
#include<string.h>
char a[110];
char s[100];
int ch[10010][26];
int val[10010] ,sz ,ans;
int id(char c) {
    return c-'a';
}
void Inse(char *s , int n ) {
    int u=0 ;
    for(int i=0;i<n;i++) {
        int c=id(s[i]);
        if(!ch[u][c]) {
            ch[u][c]=sz++;
        }
        u=ch[u][c];
    }
    if(val[u] == 0) ans++;
    val[u]=1;
}
int main()
{
    while(1) {
        gets(a);
        if(a[0] == '#') break;
        int len=strlen(a);
        a[len]=' ';
        a[len+1]=0;
        memset(ch,0,sizeof(ch));
        memset(val,0,sizeof(val));
        sz=1 ,ans=0;
        int k=0;

        for(int i=0;a[i];i++) {

            if(a[i] != ' ' ) {
                s[k++]=a[i];
            } else if(s[0] != 0){
              //  printf("%s",s);
                Inse(s , k);
                memset(s,0,sizeof(s));
                k=0;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}






联系
我们