Trie – Live with passion

644

Asif NaeemJuly 23, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;

struct node{
	bool end;
	node *nxt[2];
	node()
	{
		end=false;
		for(int i=0;i<2;i++)
		nxt[i]=NULL;
	}
}*root;
int main()
{
	string str,s;
	int id;
	node *cur,*tmp;
	int kase=1;
	while(cin>>str)
	{
		bool decodable=1;
		root=new node();
		cur=root;
		int i;
		for( i=0;i<str.size()-1;i++)
		{
			id=str[i]-'0';
			if(cur->nxt[id]==NULL)
			{
				cur->nxt[id]=new node();
			}
			cur=cur->nxt[id];
		}
		id=str[i]-'0';
		if(cur->nxt[id]==NULL)
		{
			cur->nxt[id]=new node();
		}
		cur=cur->nxt[id];
		cur->end=1;
		while(cin>>s)
		{
			if(s=="9")
			break;
			if(decodable==0)
			continue;
			tmp=root;
			int j;
			for( j=0;j<s.size()-1;j++)
			{
				id=s[j]-'0';
				if(tmp->nxt[id]==NULL)
					tmp->nxt[id]=new node();
				tmp=tmp->nxt[id];
				if(tmp->end==1)
				{
					decodable=0;
					j=s.size();
				}
			}
			id=s[j]-'0';
			if(tmp->nxt[id]==NULL)
				tmp->nxt[id]=new node();
			else
				decodable=0;
			tmp=tmp->nxt[id];
			tmp->end=1;
		}
		if(decodable)
		cout<<"Set "<<kase++<<" is immediately decodable\n";
		else
		cout<<"Set "<<kase++<<" is not immediately decodable\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

using namespace std;

struct node{

bool end;

node *nxt[2];

node()

{

end=false;

for(int i=0;i<2;i++)

nxt[i]=NULL;

}

}*root;

int main()

{

string str,s;

int id;

node *cur,*tmp;

int kase=1;

while(cin>>str)

{

bool decodable=1;

root=new node();

cur=root;

int i;

for( i=0;i<str.size()-1;i++)

{

id=str[i]-'0';

if(cur->nxt[id]==NULL)

{

cur->nxt[id]=new node();

}

cur=cur->nxt[id];

}

id=str[i]-'0';

if(cur->nxt[id]==NULL)

{

cur->nxt[id]=new node();

}

cur=cur->nxt[id];

cur->end=1;

while(cin>>s)

{

if(s=="9")

break;

if(decodable==0)

continue;

tmp=root;

int j;

for( j=0;j<s.size()-1;j++)

{

id=s[j]-'0';

if(tmp->nxt[id]==NULL)

tmp->nxt[id]=new node();

tmp=tmp->nxt[id];

if(tmp->end==1)

{

decodable=0;

j=s.size();

}

id=s[j]-'0';

if(tmp->nxt[id]==NULL)

tmp->nxt[id]=new node();

else

decodable=0;

tmp=tmp->nxt[id];

tmp->end=1;

}

if(decodable)

cout<<"Set "<<kase++<<" is immediately decodable\n";

else

cout<<"Set "<<kase++<<" is not immediately decodable\n";

}

return 0;

}

10887

Asif NaeemNovember 24, 2014

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

#define SZ 10000017

using namespace std;

char b[30];
char str[3000000][25];//3000000
int parent[10000017];
int strmap[3000000];

int gethash(char s[])
{
	int seed=31;
	int v=0;

	for(int i=0;i<strlen(s);i++)
	{
		v= v*seed+(s[i]-'0');
	}

	return (v&0x7FFFFFFF)%SZ;
}

bool insert(int position)
{
	int _hash = gethash(str[position]);
	int next=parent[_hash];
	while(next!=-1)
	{
		if(!strcmp(str[position],str[next]))
		break;
		next=strmap[next];

	}

	if(next==-1)
	{
		strmap[position]=parent[_hash];
		parent[_hash]=position;
		return 1;
	}

	return 0;
}

int main()
{
	string s;
	stringstream ss;
	int t,kase=1;
	int cnt;
	int n,m,i;
	gets(b);
	sscanf(b,"%d",&t);
	//cin>>t;
	//getchar();
	while(t--)
	{
		//getline(cin,s);
		gets(b);
		sscanf(b,"%d%d",&m,&n);
		//ss.clear();
		//ss<<s;
		//ss>>m>>n;
		cnt=0;
		memset(parent,-1,sizeof(parent));
		//memset(strmap,0,sizeof(strmap));
		for(i=0;i<m;i++)
		//getline(cin,str[i]);
		gets(str[i]);

		for(int j=0;j<n;j++)
		{
			//getline(cin,str[i]);
			gets(str[i]);
			for(int k=0;k<m;k++)
			{
				//str[i+k+1]=str[k];
				strcpy(str[i+k+1],str[k]);
				//str[i+k+1].append(str[i]);
				strcat(str[i+k+1],str[i]);
				if(insert(i+k+1))
				cnt++;
				//x++;
			}
			i=i+m+1;
		}

		cout<<"Case "<<kase++<<": "<<cnt<<"\n";

	}

	return 0;
}

#include <iostream>

#include <string>

#include <string.h>

#include <stdio.h>

#include <sstream>

#define SZ 10000017

using namespace std;

char b[30];

char str[3000000][25];//3000000

int parent[10000017];

int strmap[3000000];

int gethash(char s[])

{

int seed=31;

int v=0;

for(int i=0;i<strlen(s);i++)

{

v= v*seed+(s[i]-'0');

}

return (v&0x7FFFFFFF)%SZ;

}

bool insert(int position)

{

int _hash = gethash(str[position]);

int next=parent[_hash];

while(next!=-1)

{

if(!strcmp(str[position],str[next]))

break;

next=strmap[next];

}

if(next==-1)

{

strmap[position]=parent[_hash];

parent[_hash]=position;

return 1;

}

return 0;

}

int main()

{

string s;

stringstream ss;

int t,kase=1;

int cnt;

int n,m,i;

gets(b);

sscanf(b,"%d",&t);

//cin>>t;

//getchar();

while(t--)

{

//getline(cin,s);

gets(b);

sscanf(b,"%d%d",&m,&n);

//ss.clear();

//ss<<s;

//ss>>m>>n;

cnt=0;

memset(parent,-1,sizeof(parent));

//memset(strmap,0,sizeof(strmap));

for(i=0;i<m;i++)

//getline(cin,str[i]);

gets(str[i]);

for(int j=0;j<n;j++)

{

//getline(cin,str[i]);

gets(str[i]);

for(int k=0;k<m;k++)

{

//str[i+k+1]=str[k];

strcpy(str[i+k+1],str[k]);

//str[i+k+1].append(str[i]);

strcat(str[i+k+1],str[i]);

if(insert(i+k+1))

cnt++;

//x++;

}

i=i+m+1;

}

cout<<"Case "<<kase++<<": "<<cnt<<"\n";

}

return 0;

}

11362

Asif NaeemNovember 21, 2014

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

struct node{
	bool endofmark;
	node *next[11];

	node()
	{
		endofmark=false;
		for(int i=0;i<10;i++)
		next[i]=NULL;
	}
}*root;

int insert(string str)
{
	node *curr=root;
	int id;
	int created=0;
	for(int i=0;i<str.size();i++)
	{
		id=str[i]-'0';
		if(curr->next[id]==NULL)
		{
			curr->endofmark=false;
			curr->next[id]=new node();
			created =1;
	    }
		curr=curr->next[id];
	}
	if(created==0)
	curr->endofmark=false;
	else
	curr->endofmark=true;

	return created;
}

bool search(string str)
{
	node *curr=root;
	int len=str.size();
	int id;
	for(int i=0;i<len-1;i++)
	{
		id=str[i]-'0';
		curr=curr->next[id];
		curr->endofmark=false;
	}
	if(curr->next[str[len-1]-'0'])
	curr=curr->next[str[len-1]-'0'];
	for(int i=0;i<=9;i++)
	{
		if(curr->next[i])
		return false;
	}

	return true;
}


void delet(node *curr)
{
	for(int i=0;i<10;i++)
	{
		if(curr->next[i])
		delet(curr->next[i]);
	}
	delete(curr);
}


int main()
{
	int t,n,d,consist;
	vector<string> VB;
	string str;
	cin>>t;

	while(t--)
	{
		cin>>n;
		root=new node();
		consist=0;
		d=0;
		for(int i=0;i<n;i++)
		{
			cin>>str;
			VB.push_back(str);
			d = insert(str);
			if(d==0)
			consist=-1;
		}

	    if(consist==-1)
	    {
          cout<<"NO\n";
          VB.clear();
		 delet(root);
	     consist=0;
          continue;
        }
		for(int i=0;i<n;i++)
		{
			if(!search(VB[i]))
			{
				cout<<"NO\n";
				consist=-1;
				break;
			}
		}

		if(consist!=-1)
		cout<<"YES\n";

		VB.clear();
		delet(root);
		consist=0;
	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

#include <iostream>

#include <stdio.h>

#include <vector>

using namespace std;

struct node{

bool endofmark;

node *next[11];

node()

{

endofmark=false;

for(int i=0;i<10;i++)

next[i]=NULL;

}

}*root;

int insert(string str)

{

node *curr=root;

int id;

int created=0;

for(int i=0;i<str.size();i++)

{

id=str[i]-'0';

if(curr->next[id]==NULL)

{

curr->endofmark=false;

curr->next[id]=new node();

created =1;

}

curr=curr->next[id];

}

if(created==0)

curr->endofmark=false;

else

curr->endofmark=true;

return created;

}

bool search(string str)

{

node *curr=root;

int len=str.size();

int id;

for(int i=0;i<len-1;i++)

{

id=str[i]-'0';

curr=curr->next[id];

curr->endofmark=false;

}

if(curr->next[str[len-1]-'0'])

curr=curr->next[str[len-1]-'0'];

for(int i=0;i<=9;i++)

{

if(curr->next[i])

return false;

}

return true;

}

void delet(node *curr)

{

for(int i=0;i<10;i++)

{

if(curr->next[i])

delet(curr->next[i]);

}

delete(curr);

}

int main()

{

int t,n,d,consist;

vector<string> VB;

string str;

cin>>t;

while(t--)

{

cin>>n;

root=new node();

consist=0;

d=0;

for(int i=0;i<n;i++)

{

cin>>str;

VB.push_back(str);

d = insert(str);

if(d==0)

consist=-1;

}

if(consist==-1)

{

cout<<"NO\n";

VB.clear();

delet(root);

consist=0;

continue;

}

for(int i=0;i<n;i++)

{

if(!search(VB[i]))

{

cout<<"NO\n";

consist=-1;

break;

}

if(consist!=-1)

cout<<"YES\n";

VB.clear();

delet(root);

consist=0;

}

return 0;

}

12506

Asif NaeemNovember 21, 2014

#include <iostream>
#include <string>
#include <queue>

using namespace std;
int res;
struct node{
	int cont;
	node *next[26];

	node()
	{
		cont=0;

		for(int i=0;i<26;i++)
		next[i]=NULL;
	}

}*root;

void insert(string s)
{
	node *tmp= root;
	int len=s.size();
	int idx;
	for(int i=0;i<len;i++)
	{
		idx= s[i]-'a';
		if(tmp->next[idx]==NULL)
			tmp->next[idx]=new node();

		tmp->next[idx]->cont++;
		tmp = tmp->next[idx];
	}
}

void del(node *r)
{
	for(int i=0;i<26;i++)
		if(r->next[i]!=NULL)
		  del(r->next[i]);

	delete(r);
}

int solve()
{
	queue<node*> q;
	node *tmp= new node();

	res=0;
	q.push(root);

	while(!q.empty())
	{
		tmp = q.front();
		q.pop();

		for(int i=0;i<26;i++)
		{
			if(tmp->next[i]!=NULL)
			{
				res+=tmp->next[i]->cont;
				if((tmp->next[i]->cont)>1)
       			q.push(tmp->next[i]);
			}

		}
	}
}
int main()
{
	int t,n;
	string str;

	cin>>t;
	while(t--)
	{
		cin>>n;
		root = new node();
		for(int i=0;i<n;i++)
		{
			cin>>str;
			insert(str);
			//cout<<"inserted\n";
		}

		solve();
		cout<<res<<"\n";
		del(root);
	}

	return 0;
}

#include <iostream>

#include <string>

#include <queue>

using namespace std;

int res;

struct node{

int cont;

node *next[26];

node()

{

cont=0;

for(int i=0;i<26;i++)

next[i]=NULL;

}

}*root;

void insert(string s)

{

node *tmp= root;

int len=s.size();

int idx;

for(int i=0;i<len;i++)

{

idx= s[i]-'a';

if(tmp->next[idx]==NULL)

tmp->next[idx]=new node();

tmp->next[idx]->cont++;

tmp = tmp->next[idx];

}

void del(node *r)

{

for(int i=0;i<26;i++)

if(r->next[i]!=NULL)

del(r->next[i]);

delete(r);

}

int solve()

{

queue<node*> q;

node *tmp= new node();

res=0;

q.push(root);

while(!q.empty())

{

tmp = q.front();

q.pop();

for(int i=0;i<26;i++)

{

if(tmp->next[i]!=NULL)

{

res+=tmp->next[i]->cont;

if((tmp->next[i]->cont)>1)

q.push(tmp->next[i]);

}

int main()

{

int t,n;

string str;

cin>>t;

while(t--)

{

cin>>n;

root = new node();

for(int i=0;i<n;i++)

{

cin>>str;

insert(str);

//cout<<"inserted\n";

}

solve();

cout<<res<<"\n";

del(root);

}

return 0;

}

Category: Trie

644

10887

11362

12506

Archives

Categories