hihocoder Trieツリー

3224 ワード

C++ Trieツリー

時間制限:
10000ms
単一点時限:
1000ms
メモリの制限:
256MB
説明
HiさんとHoさんは良い友达で、情报化社会に生まれた彼らはプログラミングに大きな兴味を持って、彼らはお互いに助け合うことを约束して、プログラミングの学习の道の上でいっしょに进みます.
この日、彼らは辞書に出会ったので、HiさんはHoさんにその古典的な質問をしました.「Hoさん、私が与えた文字列ごとに、この辞書の中でこの文字列で始まるすべての単語を見つけることができますか?」
百戦錬磨のホーは答えた.「どうしてできないの.文字列を1つあげるたびに、辞書の中のすべての単語を順番に巡り、あなたがくれた文字列がこの単語の接頭辞ではないかをチェックします.」
Hiちゃんは笑って言いました:“あなた、やはり若すぎます!~もしこの辞書の中に10万の単語があるとしたら、私はあなたに1万回聞いて、あなたはどの年のどの月に行かなければなりませんか?”
Hoちゃんは頭を下げて計算して、その山の0を見て、すぐに自分が一生上に使うと感じました...
HiちゃんはHoちゃんの顔を見て、「知識のレベルを上げましょう.木のようなデータ構造を知っていますか」と笑い続けた.
Hoさんは考えて、「知っています~それは基礎的なデータ構造で、ここで言ったように!」と言いました.
Hiさんは満足そうにうなずいて、「じゃあ、辞書全体を木で表す方法を知っていますか」と言った.
Hoさんは首を横に振って自分が分からないことを示した.
ヒント1:Trieツリーの作成
「ほら、私たちは今このような木を手に入れました.では、もし私があなたに文字列apをあげたら、どうやってapで始まる単語を見つけますか?」Hiさんはまた学校のHoさんを受験し始めました.
「うん...すべての単語を一つ一つ巡る?」Hoちゃんはやはり自分が最初に出したアルゴリズムを忘れない.
「ばか!この木は白く建てられたのか!」HiちゃんはHoちゃんを教訓にして、「よく見て!」と続けた.
ヒント2:Trieツリーの使用方法
ヒント3:Trieツリーを作成するときに統計を同時に行う!
「じゃあ今!早くコードで実現しましょう!」Hiちゃんはこう言いました.
入力
第1行目を正の整数nとして入力し、辞書の大きさを表し、その後n行、各行に1つの単語(英語の単語であることは保証されず、火星文の単語である可能性もありますよ)を10個以下の小文字の英字からなり、同じ単語が存在する可能性があり、この場合は異なる単語と見なすべきです.次の行は正の整数mで、小Hiの問い合わせの回数を表し、その後m行で、各行に10個を超えない小文字の英字からなり、小Hiの問い合わせを表す文字列である.
20%のデータではn,m<=10,辞書のアルファベットサイズ<=2である.
60%のデータのうちn,m<=1000,辞書のアルファベットサイズ<=5.
100%のデータでn,m<=10000000,辞書のアルファベットサイズ<=26.
本題は合格したデータ量でランキングしますよ～
しゅつりょく
小Hiの各問合せについて、小Hiで与えられた文字列を接頭辞とする辞書の単語の個数を表す整数Ansが出力される.
サンプル入力

5
babaab
babbbaaaa
abba
aaaaabaa
babaababb
5
babb
baabaaa
bab
bb
bbabbaab

サンプル出力

この問題は、私が最後にTrieツリーで使用したメモリを解放すると、MLEエラー(Memory Limite Exceede)が発生し、構造関数を呼び出さなければ通過できます.

#include<iostream>
#include<string>
using namespace std;

struct TrieNode{
	bool isword;//            
	unsigned int count;
	TrieNode *next[26];//    
	TrieNode():isword(false),count(0){
		for(int i=0;i<26;i++)
		next[i]=NULL;
	}
};

class TrieTree{
public:
	TrieTree()
	{
		root=new TrieNode();
	}
	~TrieTree()
	{
		//destroy(root);
	}
	void insert(const char *s);//  
	unsigned int  find(const char *s);//  
	void destroy(TrieNode *r);
private:
	TrieNode *root;
	
};
//s     
void TrieTree::insert(const char *s)
{
	TrieNode *r=root;
	while(*s)
	{
		if(!r->next[*s-'a'])//      
		{
			TrieNode *t=new TrieNode();//      
			r->next[*s-'a']=t;
		}
		r->count++;
		r=r->next[*s-'a'];
		s++;
	}
	r->isword=true;//     
	r->count++;
}
	//      s
unsigned int  TrieTree::find(const char *s)
{
	TrieNode *r=root;
	while(*s)
	{
		if(!r->next[*s-'a'])
		return 0;
		r=r->next[*s-'a'];
		s++;
	}
	return r->count;
}
void TrieTree::destroy(TrieNode *r)
{
	for(int i=0;i<26;i++)
	{
		if(r->next[i]!=NULL)
			destroy(r->next[i]);
	}
	delete r;
}

int main()
{
	string s;//  
	unsigned int n;//     
	unsigned int m;//       
	TrieTree T;
	cin>>n;
	for(unsigned int i=0;i<n;i++)
	{
		cin>>s;//
		T.insert(s.c_str());
	}
	cin>>m;
	for(unsigned int i=0;i<m;i++)
	{
		cin>>s;
		cout<<T.find(s.c_str())<<endl;
	}
	return 0;
}

redis性能向上とNagelアルゴリズム

Redis質疑応答