hdu1251

maksyuki 发表于 oj 分类，标签: 字符串-Trie树

15 9月 2015

统计难题

Problem Description

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

Output

对于每个提问,给出以该字符串为前缀的单词的数量.

Sample Input

banana

band

bee

absolute

acm

band

abc

Sample Output

Author

Ignatius.L

题目类型：trie树

算法分析：每个节点使用一个变量cnt，表示以这个字符串为前缀的字符串的个数，在每次插入新字符串的时候可以不断更新，注意使用G++提交会MLE！！！

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 1e9 + 7;
const int maxn = 26;

struct Trie
{
    Trie *next[maxn];
    int cnt;
    Trie ()
    {
        memset (next, 0, sizeof (next));
        cnt = 1;
    }
};

Trie *root;

void Init ()
{
    root = new Trie ();
}

void Insert (char *s)
{
    if (!s[0])
        return ;

    Trie *p = root;
    for (int i = 0; s[i]; i++)
    {
        if (!p -> next[s[i]-'a'])
        {
            p -> next[s[i]-'a'] = new Trie;
            p = p -> next[s[i]-'a'];
        }

        else
        {
            p = p -> next[s[i]-'a'];
            p -> cnt = p -> cnt + 1;
        }
    }
}

int Query (char *s)
{
    if (!s[0])
        return 0;

    Trie *p = root;
    for (int i = 0; s[i]; i++)
    {
        if (!p -> next[s[i]-'a'])
            return 0;

        p = p -> next[s[i]-'a'];
    }

return p -> cnt;
}

void DelTrie (Trie *t)
{
    if (!t) return ;

    for (int i = 0; i < maxn; i++)
    {
        if (t -> next[i])
            DelTrie (t -> next[i]);
    }
    delete t;
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    char s[maxn];
    Init ();

    while (gets (s))
    {
        if (!strcmp (s, ""))
            break;

        Insert(s);
    }

    while (scanf ("%s", s) != EOF)
    {
        printf ("%d\n", Query (s));
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 1e9 + 7;

const int maxn = 26;

struct Trie

{

Trie *next[maxn];

int cnt;

Trie ()

{

memset (next, 0, sizeof (next));

cnt = 1;

}

};

Trie *root;

void Init ()

{

root = new Trie ();

}

void Insert (char *s)

{

if (!s[0])

return ;

Trie *p = root;

for (int i = 0; s[i]; i++)

{

if (!p -> next[s[i]-'a'])

{

p -> next[s[i]-'a'] = new Trie;

p = p -> next[s[i]-'a'];

}

else

{

p = p -> next[s[i]-'a'];

p -> cnt = p -> cnt + 1;

}

int Query (char *s)

{

if (!s[0])

return 0;

Trie *p = root;

for (int i = 0; s[i]; i++)

{

if (!p -> next[s[i]-'a'])

return 0;

p = p -> next[s[i]-'a'];

}

return p -> cnt;

}

void DelTrie (Trie *t)

{

if (!t) return ;

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

{

if (t -> next[i])

DelTrie (t -> next[i]);

}

delete t;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

char s[maxn];

Init ();

while (gets (s))

{

if (!strcmp (s, ""))

break;

Insert(s);

}

while (scanf ("%s", s) != EOF)

{

printf ("%d\n", Query (s));

}

return 0;

}

hdu1240

hdu1395

超客的水墨烟雨

hdu1251

统计难题

分类目录

标签云

书签

近期评论

2024年12月
一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31