hdu1251题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1251

统计难题

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others)
Total Submission(s): 65063    Accepted Submission(s): 22438

Problem Description

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

Input

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

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

Output

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

Sample Input

banana 
band 
bee 
absolute 
acm
 
ba 
b 
band 
abc

Sample Output

2 3 1 0

 解题思路：

在建字典树的时候用一个数组sum[]记录每个节点被访问过的次数，这样就可以在查询的时候找到该节点输出该节点的sum[]值即可

 

ac代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <fstream>
typedef long long ll;
const int maxn=2e6+5;
using namespace std;
int tot=0;//总节点数
int tree[maxn][30],words[maxn],sum[maxn];
string s,ss;
void insert()
{
    int root=0;
    for(int i=0;i<s.length();i++)
    {
        int id=s[i]-'a';
        if(!tree[root][id]) tree[root][id]=++tot;
        root=tree[root][id];
        sum[root]++;//记录节点访问次数
    }
    //words[root]=1;//单词标记
}
int query(string ss)
{
    int len=ss.length(),root=0;
    for(int i=0;i<len;i++)
    {
        int id=ss[i]-'a';
        if(!tree[root][id]) return 0;//没有出现过
        root=tree[root][id];
    }
    return sum[root];
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    while(getline(cin,s))
    {
        if(s[0]=='\0')//或者写成if(s.length()==0)
        {
            while(cin>>ss)
                printf("%d\n",query(ss));
        }
        else insert();//建树
    }
    return 0;
}

 

poj2001题目地址：http://poj.org/problem?id=2001

题目：

                                                    Shortest Prefixes

Time Limit: 1000MS   Memory Limit: 30000K
Total Submissions: 22927   Accepted: 9737

Description

求唯一标识一个单词的前缀，这个前缀可以是单词本身，如样例中的car

Sample Input

carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate

Sample Output

carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona

解题思路：

先建立字典树，在建树过程中标记每个节点出现的次数，在查询的时候如何第一碰到只出现一次的节点或者已经到了这个单词的末尾，那么就输出相应的结果

 

ac代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxn=1e6+5;
using namespace std;
int tot=0;
int tree[maxn][30],cnt[maxn];
string s;
void build(string s)
{
    int root=0,len=s.length();
    for(int i=0;i<len;i++)
    {
        int id=s[i]-'a';
        if(!tree[root][id]) tree[root][id]=++tot;
        root=tree[root][id];
        cnt[root]++;
    }
    cnt[root]++;
}
string query(string s)
{
    int len=s.length(),root=0;
    string ans="";
    for(int i=0;i<len;i++)
    {
        int id=s[i]-'a';
        ans+=s[i];
        root=tree[root][id];
        if(ans==s || cnt[root]==1)//单词
            return ans;
    }
}
int main() {
    //freopen("/Users/zhangkanqi/Desktop/11.txt", "r", stdin);
    queue<string> q;
    while (cin >> s)
    {
        build(s);
        q.push(s);
    }
    while(!q.empty())
    {
        string str=q.front();q.pop();
        cout<<str<<" "<<query(str)<<endl;
    }
    return 0;
}

 

POJ3630题目地址： http://poj.org/problem?id=3630

题目：

                                                                          Phone List

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 36604   Accepted: 10408

Description

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let's say the phone catalogue listed these numbers:

  • Emergency 911
  • Alice 97 625 999
  • Bob 91 12 54 26

In this case, it's not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob's phone number. So this list would not be consistent.

Sample Input

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

Sample Output

NO
YES

ac代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxn=1e5;
using namespace std;
int tot=0;
int tree[maxn][30],cnt[maxn],words[maxn];
string s;
bool ans=true;
void build(string s)
{
    int root=0,len=s.length();
    for(int i=0;i<len;i++)
    {
        int id=s[i]-'0';
        if(!tree[root][id]) tree[root][id]=++tot;
        root=tree[root][id];
        cnt[root]++;
    }
    words[root]=1;
}
bool query()
{
    for(int i=1;i<=tot;i++)
        if(words[i] && cnt[i]>1)
            return false;
    return true;
}
int main() {
    //freopen("/Users/zhangkanqi/Desktop/11.txt", "r", stdin);
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        ans=true;tot=0;
        memset(words,0,sizeof(words));
        memset(tree,0,sizeof(tree));
        memset(cnt,0,sizeof(cnt));
        while(n--)
        {
            cin>>s;
            build(s);
        }
        printf("%s\n",query()?"YES":"NO");
    }
    return 0;
}