hdu----单词数

柔情只为你懂 2022-06-16 10:19 151阅读 0赞

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

Input

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

Output

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

Sample Input

you are my friend
    #

Sample Output

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int MAXN = 100000;
    struct Trie
    {
        int next[26];
        int val;
    } tree[MAXN];
    int nxt,sum;
    char str[MAXN],ss[100];
    void Insert(char *s)
    {
        int rt=0, len = strlen(s);
        for(int i=0; i < len; i++)
        {
            int c=s[i]-'a';
            if(!tree[rt].next[c])
                tree[rt].next[c]=nxt++;
            rt = tree[rt].next[c];
        }
        if(!tree[rt].val)
        sum++;
        tree[rt].val++;
    }
    int main()
    {
        while(gets(str)&&str[0]!='#')
        {
            sum=0;
            nxt = 1;
            memset(tree,0, sizeof(tree));
            int len=strlen(str);
            for(int i=0;i<len;i++)
            {
                while(str[i++]==' ');
                i--;
                if(i==len)
                    break;
                int j=0;
                while(str[i]!=' '&&i<len)
                    ss[j++]=str[i++];
                ss[j]='\0';
                Insert(ss);
            }
            printf("%d\n",sum);
        }
        return 0;
    }

我的注释理解

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int MAXN = 100000;
    struct Trie
    {
        int next[26];
        int val;
    } tree[MAXN];
    int nxt,sum;
    char str[MAXN],ss[100];
    void Insert(char *s)
    {
        int rt=0, len = strlen(s);
        for(int i=0; i < len; i++)//这个循环是建立字典树的模板
        {
            int c=s[i]-'a';
            if(!tree[rt].next[c])
                tree[rt].next[c]=nxt++;
            rt = tree[rt].next[c];
        }
        if(!tree[rt].val)//tree[rt].val如果为0就说明是个新单词(即之前没出现过)，单词数sum就加1
            //如果大于0就说明是同一个单词（即出现过），sum不加
        sum++;
        tree[rt].val++;
    }
    int main()
    {
        while(gets(str)&&str[0]!='#')
        {
            sum=0;
            nxt = 1;
            memset(tree,0, sizeof(tree));
            int len=strlen(str);
            for(int i=0;i<len;i++)//将单词拿出来建立字典树
            {
                while(str[i++]==' ');
                i--;
                if(i==len)
                    break;
                int j=0;
                while(str[i]!=' '&&i<len)
                    ss[j++]=str[i++];
                ss[j]='\0';
                Insert(ss);
            }
            printf("%d\n",sum);
        }
        return 0;
    }