字典树--统计难题

统计难题

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others)

Total Submission(s): 54150    Accepted Submission(s): 18929

Problem Description

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

Input

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

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

Output

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

Sample Input

banana band bee absolute acm ba b band abc

Sample Output

2 3 1 0

Author

Ignatius.L

Recommend

Ignatius.L   |   We have carefully selected several similar problems for you:  1075 1247 1671 1298 1800 

AC代码 ：

#include <cstdio>
#include <cstring>
#include <map>
#include <iostream>
using namespace std;

int main(){
    int i, len;
    char str[10];//存放输入字符 
    map<string, int> m;
    while( gets(str) ){//输入单词表 
        len = strlen(str);
        if( !len )
            break;
        for(i = len; i > 0; i--){//从后往前，将所有前缀+1 
            str[i] = '\0';
            m[str]++;
        }
    }
    while( gets(str) )//输入查询字符串 
        printf("%d\n", m[str]);
    return 0;
}
 
           

真滴奇怪，字典树模板题，用字典树做居然超空间了，不过还是可以参考下：

#include<stdio.h>
#include<string.h>

struct node{
    int cnt;//用于记录该前缀出现次数 
    node *next[27];//保存子节点 
    node(){
    	cnt=0;
    	memset(next,0,sizeof(next));
    }
};

void insert(node *root,char s[]){//插入单词 
    int i=0;
    node *p=root;//创建一个指向字符串首位的node类型的指针指向root节点 
    while(s[i]){//按照字典树的方式一位一位的插入 
        int j=s[i++]-'a';
        if(p->next[j]==NULL)//当还没有该字母的出现，就创建一个 
			p->next[j]=new node();
        p=p->next[j]; 
        p->cnt+=1;//该前缀出现次数+1 
    }
}

int judge(node *root,char s[]){//比对 
    int i=0;
    node *p=root;
    int HowMany=0;
    while(s[i]){
        int j=s[i++]-'a';
        if(p->next[j]==NULL){
            HowMany=0;break;
        }
        p=p->next[j];
        HowMany=p->cnt;
    }
    return HowMany; 
}

int main(){
    node *root=new node();//创建一个字典树的根节点 
    char word[10];//存放单词表 
    char cur[10];//存放查询前缀 
    while(gets(word)){//输入单词表 
        if(strcmp(word,"")==0) break;//结束标志为输入为空 
        insert(root,word);
    }
    while(gets(cur)){//输入傲查找的字符串前缀 
        printf("%d\n",judge(root,cur));
    }
    return 0;
}
           

emmm，换成数组的方式来建树，就可以AC了。。

#include<string.h>
#include<stdio.h>

int trie[400001][27],sum[400001];
int id;

void insert(char *s){
	int len=strlen(s);
	int root=0;
	for(int i=0;i<len;i++){
		int x=s[i]-'a';
		if(trie[root][x]==0)
			trie[root][x]=++id;//trie数组中放的是它的id（编号） 
		sum[trie[root][x]]++;//访问该节点（编号）的次数sum++ 
		root=trie[root][x];//转移到下一个节点 
	}
}

int search(char *s){
	int len=strlen(s);
	int root=0;
	for(int i=0;i<len;i++){//遍历得出 
		int x=s[i]-'a';
		if(trie[root][x]==0)
			return 0;//不存在该节点，直接说明没有以此的前缀 
		root=trie[root][x];//否则root = 该节点的编号 
	}
	return sum[root];//sum[i] --> 存放的是插入时访问点i的次数 
}

int main(){
	id=0;//初始化编号 
	char s[11];
	while(gets(s)){
		if(strcmp(s,"")==0)
			break;
   		insert(s);
   	}
   	while(scanf("%s",s)!=EOF){
   		printf("%d\n",search(s));
   	}
   	return 0;
}