TrieのC++実装およびHDU 1251,hdu 1671
16192 ワード
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
using namespace std;
template<int Size>
struct trie_node{
bool terminable; //
int node; //
trie_node *child[Size]; //
trie_node():terminable(false), node(0){
memset(child,0,sizeof(child)); //
}
};
template<int Size,typename Index>
class trie{
public:
//
typedef trie_node<Size> node_type;
typedef trie_node<Size> *link_type;
//
trie(Index i=Index()):index(i){ }
// ,
void clear(){
clear_node(root);
for(int i=0;i<Size;i++)
root.child[i]=0;
}
//
template<typename Iterator>
void insert(Iterator begin,Iterator end){
link_type cur= &root;//
while(begin!=end){
if(!cur->child[index[*begin]]){//
cur->child[index[*begin]]=new node_type;
cur->node++; // ,
}
cur=cur->child[index[*begin]]; //
begin++; // !
}
cur->terminable=true;
}
// c
void insert(const char * str){
insert(str,str+strlen(str));
}
//
template <typename Iterator>
bool find(Iterator begin,Iterator end){
link_type cur=&root;
while(begin!=end){
if(!cur->child[index[*begin]]) // !!!
return false;
cur=cur->child[index[*begin]];
begin++;
}
return cur->terminable; //
}
// c
bool find(const char *str){
return find(str,str+strlen(str));
}
//
template<typename Iterator>
bool earse (Iterator begin,Iterator end){
bool result;
earse_node(begin,end,root,result);
return result;
}
//c
bool erase(char *str){
return earse(str,str+strlen(str));
}
template<typename Functor>
void traverse(Functor &execute =Functor()){
visit_node(root,execute);
}
private:
//
template<typename Functor>
void visit_node(node_type cur,Functor &execute){
execute(cur);
for(int i=0;i<Size;i++){//dfs
if(cur.child[i]==0) continue;
visit_node(*cur.child[i],execute);
}
}
//
void clear_node(node_type cur){
for(int i=0;i<Size;i++){
if(cur.child[i]==0)continue; //
clear_node(*cur.child[i]);
delete cur.childe[i];
cur.child[i]=0;
if(--cur.node==0) break; //
}
}
//
template<typename Iterator>
bool earse_node(Iterator begin ,Iterator end,node_type &cur,bool &result){
if(begin==end){
result=cur.terminable;
cur.terminalbe=false;
return cur.node==0;
}
// , ,
if(cur.child[index[*begin ]]==0) return !(result=false);
else if(earse_node(begin+1,end,*(cur.child[index[*begin]]),result)){
delete cur.child[index[*begin]];
cur.child[index[*begin]]=0;
if(--cur.node==0&&cur.terminable==false ) return true;
}
return false;
}
//
node_type root;
// , hash
Index index;
};
class IndexClass{
public:
int operator[](const char key){
return key%26; //
}
};
int main(){
trie<26,IndexClass> t;
t.insert("tree");
t.insert("tea");
t.insert("act");
t.insert("adv");
t.insert("ate");
if(t.find("tree")){
cout<<"find!";
}
char str[50];
while(scanf("%s",str)!=EOF){
if(t.find(str)==1){
cout<<"find"<<endl;
}
}
return 0;
}
ほとんどのリファレンスhttp://blog.csdn.net/luxiaoxun/article/details/7937589
その後1251裸問題でテストしました.
Acは思い切って嬉しいですね!
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
using namespace std;
template<int Size>
struct trie_node{
bool terminable; //
int node; //
trie_node *child[Size]; //
trie_node():terminable(false), node(0){
memset(child,0,sizeof(child)); //
}
};
template<int Size,typename Index>
class trie{
public:
//
typedef trie_node<Size> node_type;
typedef trie_node<Size> *link_type;
//
trie(Index i=Index()):index(i){ }
// ,
void clear(){
clear_node(root);
for(int i=0;i<Size;i++)
root.child[i]=0;
}
//
template<typename Iterator>
void insert(Iterator begin,Iterator end){
link_type cur= &root;//
while(begin!=end){
if(cur->child[index[*begin]]){//
cur=cur->child[index[*begin]];
++(cur->node);
}else{
cur->child[index[*begin]]=new node_type;
++(cur->child[index[*begin]]->node);
cur=cur->child[index[*begin]];
}
begin++; // !
}
cur->terminable=true;
}
// c
void insert(const char * str){
insert(str,str+strlen(str));
}
//
template <typename Iterator>
bool find(Iterator begin,Iterator end){
link_type cur=&root;
while(begin!=end){
if(!cur->child[index[*begin]]) // !!!
return false;
cur=cur->child[index[*begin]];
begin++;
}
return cur->terminable; //
}
template <typename Iterator>
int findNum(Iterator begin,Iterator end){
link_type cur=&root;
while(begin!=end){
if(!cur->child[index[*begin]]) // !!!
return 0;
cur=cur->child[index[*begin]];
begin++;
}
return cur->node; //
}
// c
int findNum(const char *str){
return findNum(str,str+strlen(str));
}
// c
bool find(const char *str){
return find(str,str+strlen(str));
}
//
template<typename Iterator>
bool earse (Iterator begin,Iterator end){
bool result;
earse_node(begin,end,root,result);
return result;
}
//c
bool erase(char *str){
return earse(str,str+strlen(str));
}
template<typename Functor>
void traverse(Functor &execute =Functor()){
visit_node(root,execute);
}
private:
//
template<typename Functor>
void visit_node(node_type cur,Functor &execute){
execute(cur);
for(int i=0;i<Size;i++){//dfs
if(cur.child[i]==0) continue;
visit_node(*cur.child[i],execute);
}
}
//
void clear_node(node_type cur){
for(int i=0;i<Size;i++){
if(cur.child[i]==0)continue; //
clear_node(*cur.child[i]);
delete cur.childe[i];
cur.child[i]=0;
if(--cur.node==0) break; //
}
}
//
template<typename Iterator>
bool earse_node(Iterator begin ,Iterator end,node_type &cur,bool &result){
if(begin==end){
result=cur.terminable;
cur.terminalbe=false;
return cur.node==0;
}
// , ,
if(cur.child[index[*begin ]]==0) return !(result=false);
else if(earse_node(begin+1,end,*(cur.child[index[*begin]]),result)){
delete cur.child[index[*begin]];
cur.child[index[*begin]]=0;
if(--cur.node==0&&cur.terminable==false ) return true;
}
return false;
}
//
node_type root;
// , hash
Index index;
};
class IndexClass{
public:
int operator[](const char key){
return key%26; //
}
};
int main(){
trie<26,IndexClass> t;
char s[11];
//freopen("in.txt","r",stdin);
while(gets(s) && s[0])
{
t.insert( s);
}
while(gets(s))
{
printf("%d
", t.findNum(s));
}
return 0;
}
HDU1671
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<vector>
using namespace std;
#define MAXN 10
template<int Size>
struct trie_node
{
bool terminable; //
int node; //
trie_node *child[Size]; //
trie_node():terminable(false), node(0)
{
memset(child,0,sizeof(child)); //
}
};
template<int Size,typename Index>
class trie
{
public:
//
typedef trie_node<Size> node_type;
typedef trie_node<Size> *link_type;
//
trie(Index i=Index()):index(i) { }
// ,
void clear()
{
clear_node(root);
for(int i=0; i<Size; i++)
root.child[i]=0;
}
//
template<typename Iterator>
void insert(Iterator begin,Iterator end)
{
link_type cur= &root;//
while(begin!=end)
{
if(cur->child[index[*begin]]) //
{
cur=cur->child[index[*begin]];
cur->node++;
}
else
{
cur->child[index[*begin]]=new node_type;
cur->child[index[*begin]]->node++;
cur=cur->child[index[*begin]];
}
begin++; // !
}
cur->terminable=true;
}
// c
void insert(const char * str)
{
insert(str,str+strlen(str));
}
//
template<typename Iterator>
bool insert2(Iterator begin,Iterator end)
{
link_type cur= &root;//
bool flag=0;
while(begin!=end)
{
if(cur->child[index[*begin]]) //
{
if(cur->child[index[*begin]]->terminable==true){
flag=1;
}
cur=cur->child[index[*begin]];
cur->node++;
}
else
{
cur->child[index[*begin]]=new node_type;
cur->child[index[*begin]]->node++;
cur=cur->child[index[*begin]];
}
begin++; // !
}
cur->terminable=true;
return flag;
}
// c
bool insert2(const char * str)
{
return insert2(str,str+strlen(str));
}
//
template <typename Iterator>
bool find(Iterator begin,Iterator end)
{
link_type cur=&root;
while(begin!=end)
{
if(!cur->child[index[*begin]]) // !!!
return false;
cur=cur->child[index[*begin]];
begin++;
}
return cur->terminable; //
}
// c
bool find(const char *str)
{
return find(str,str+strlen(str));
}
//
template <typename Iterator>
int findNum(Iterator begin,Iterator end)
{
link_type cur=&root;
while(begin!=end)
{
if(!cur->child[index[*begin]]) // !!!
return 0;
cur=cur->child[index[*begin]];
begin++;
}
return cur->node; //
}
// c
int findNum(const char *str)
{
return findNum(str,str+strlen(str));
}
//
template <typename Iterator>
bool findPre(Iterator begin,Iterator end)
{
link_type cur=&root;
while(begin!=end)
{
if(!cur->child[index[*begin]]) // !!!
return false;
if(cur->terminable) break;
cur=cur->child[index[*begin]];
begin++;
}
return begin!=end; //
}
bool findPre(const char *str){
return findPre(str,str+strlen(str));
}
//
template<typename Iterator>
bool earse (Iterator begin,Iterator end)
{
bool result;
earse_node(begin,end,root,result);
return result;
}
//c
bool erase(char *str)
{
return earse(str,str+strlen(str));
}
template<typename Functor>
void traverse(Functor &execute =Functor())
{
visit_node(root,execute);
}
private:
//
template<typename Functor>
void visit_node(node_type cur,Functor &execute)
{
execute(cur);
for(int i=0; i<Size; i++) //dfs
{
if(cur.child[i]==0) continue;
visit_node(*cur.child[i],execute);
}
}
//
void clear_node(node_type cur)
{
for(int i=0; i<Size; i++)
{
if(cur.child[i]==0)continue; //
clear_node(*cur.child[i]);
delete cur.child[i];
cur.child[i]=0;
if(--cur.node==0) break; //
}
}
//
template<typename Iterator>
bool earse_node(Iterator begin ,Iterator end,node_type &cur,bool &result)
{
if(begin==end)
{
result=cur.terminable;
cur.terminalbe=false;
return cur.node==0;
}
// , ,
if(cur.child[index[*begin ]]==0) return !(result=false);
else if(earse_node(begin+1,end,*(cur.child[index[*begin]]),result))
{
delete cur.child[index[*begin]];
cur.child[index[*begin]]=0;
if(--cur.node==0&&cur.terminable==false ) return true;
}
return false;
}
//
node_type root;
// , hash
Index index;
};
class IndexClass
{
public:
int operator[](const char key)
{
return key%MAXN; //
}
};
char s[10000][11];
int main()
{
trie<MAXN,IndexClass> t;
int T,n,i;
// freopen("in.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
t.clear();
for(i=0;i<n;i++){
scanf("%s",s[i]);
t.insert(s[i]);
}
for(i=0;i<n;i++){
if(t.findPre(s[i])){
puts("NO");
break;
}
}
if(i==n) puts("YES");
}
return 0;
}