HDU-2072-单词数(字典树)

链接:

https://vjudge.net/problem/HDU-2072

题意:

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

思路:

字典树, 插入的时候判断是否为重复插入即可.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

//#include <memory.h>

#include <queue>

#include <set>

#include <map>

#include <algorithm>

#include <math.h>

#include <stack>

#include <string>

#include <assert.h>

#include <iomanip>

#include <iostream>

#include <sstream>

#define MINF 0x3f3f3f3f

using namespace std;

typedef long long LL;

const int INF = 1e9;

const int MAXN = 1e6+10;

int cnt, n;

string word;

struct Node

{

    bool Ends;

    int Next[30];

    void Init()

    {

        Ends = false;

        memset(Next, 0, sizeof(Next));

    }

}Trie[MAXN];

bool Insert(string val)

{

    int root = 0;

    int len = val.size();

    for (int i = 0;i < len;i++)

    {

        if (Trie[root].Next[val[i]-'a'] == 0)

        {

            Trie[root].Next[val[i]-'a'] = ++cnt;

            Trie[cnt].Init();

        }

        root = Trie[root].Next[val[i]-'a'];

    }

    if (Trie[root].Ends)

        return false;

    Trie[root].Ends = true;

    return true;

}

int main()

{

    while (getline(cin, word))

    {

        if (word[0] == '#')

            break;

        cnt = 0;

        int ans = 0;

        Trie[0].Init();

        stringstream ss(word);

        while (ss >> word)

        {

            if (Insert(word))

                ans++;

        }

        printf("%d\n", ans);

        for (int i = 0;i <= cnt;i++)

            Trie[i].Init();

    }

    return 0;

}