Trie+DFS(1251)

2892 ワード

統計上の課題
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others) Total Submission(s): 30258 Accepted Submission(s): 11769
Problem Description
Ignatiusは最近、ある文字列を接頭辞とする単語の数(単語自体も自分の接頭辞)を統計するように要求された.

Input
入力データの第1部は1枚の単語表で、1行ごとに1つの単語、単語の長さは10を超えないで、それらは先生がIgnatiusに渡して統計した単語を代表して、1つの空行は単語表の終わりを代表します.第2部は一連の質問で、各行は1つの質問で、各質問はすべて1つの文字列です.
注意:本題はテストデータのセットだけで、ファイルが終わるまで処理します.

Output
各質問に対して、その文字列を接頭辞とする単語の数を与える.

Sample Input

 
   
     banana band bee absolute acm ba b band abc

Sample Output

 
   
     2 3 1 0

注意读入的技巧，以及用G++交MLE，用C++交却AC。。

/*------------------Header Files------------------*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
/*------------------Definitions-------------------*/
#define LL long long
#define uLL unsigned long long
#define PI acos(-1.0)
#define INF 0x3F3F3F3F
#define MOD 9973
#define MAX 105
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
/*---------------------Work-----------------------*/
struct node
{
	bool isWord;
	node *next[26];
	node()
	{
		isWord=false;
		memset(next,0,sizeof(next));	
	}	
};
void insert(node *rt,char *s)
{
	int i=0;
	node *p=rt;
	while(s[i])
	{
		int temp=s[i++]-'a';
		if(p->next[temp]==NULL) p->next[temp]=new node();
		p=p->next[temp];
	}
	p->isWord=true;
}
int sum;
void DFS(node *rt)
{
	if(rt->isWord) sum++;
	for(int i=0;i<26;i++)
	{
		if(rt->next[i]) DFS(rt->next[i]);
	}
}
int cnt(node *rt,char *s)
{
	int i=0;
	node *p=rt;
	while(s[i])
	{
		int temp=s[i++]-'a';
		if(p->next[temp]==NULL) return 0;
		p=p->next[temp];
	}
	DFS(p);
}
void work()
{
	node *rt=new node();
	char temp[15];
	while(gets(temp)&&strlen(temp)) //    
	{
		if(temp[0]=='\0') break;
		insert(rt,temp);
	}
	while(scanf("%s",temp)==1)
	{
		sum=0;
		cnt(rt,temp);
		printf("%d
",sum);
	}
}
/*------------------Main Function------------------*/
int main()
{
	//freopen("test.txt","r",stdin);
	work();
	return 0;
}

SparkのRDD操作と説明_2

JAVAは2つの日付の差の日数を比較します