tanu.psaxena.bce10@itbhu.ac.in
BAN USER#include<iostream>
using namespace std;
struct node
{
char val;
node *lc;
node *rc;
}*root;
void setLeft(node *a,char c)
{
node *temp=new node();
temp->val=c;
temp->lc=NULL;
temp->rc=NULL;
a->lc=temp;
}
void setRight(node *a,char c)
{
node *temp=new node();
temp->val=c;
temp->lc=NULL;
temp->rc=NULL;
a->rc=temp;
}
void buildTree(node *root,string s,int& len)
{
if(root->val>=65&&root->val<=90)
{
len--;
setRight(root,s[len]);
buildTree(root->rc,s,len);
len--;
setLeft(root,s[len]);
buildTree(root->lc,s,len);
}
}
void checkLeaf(node *a,int &count)
{
if(a->val>=97&&a->val<=122)
{
count++;
return;
}
checkLeaf(a->lc,count);
checkLeaf(a->rc,count);
}
void explorePath(node *root,string a,int pos,int &count,int k)
{
if(root==NULL)
return;
if(pos==k-1)
{
if(root->val!=a[pos])
{
explorePath(root->lc,a,pos,count,k);
explorePath(root->rc,a,pos,count,k);
}
if(root->val==a[pos]&&(root->val>=97&&root->val<=122))
{
count++;
return;
}
else if(root->val==a[pos]&&(root->val>=65&&root->val<=90))
{
checkLeaf(root->lc,count);
checkLeaf(root->rc,count);
return;
}
}
else
{if(root->val==a[pos])
pos++;
explorePath(root->lc,a,pos,count,k);
explorePath(root->rc,a,pos,count,k);
}
}
int main()
{
int n,k;
string s,a;
cin>>n>>s>>k>>a;
n--;
root=new node();
root->val=s[n];
root->lc=root->rc=NULL;
buildTree(root,s,n);
int count=0;
explorePath(root,a,0,count,k);
cout<<count;
return 0;
}
- tanu.psaxena.bce10@itbhu.ac.in November 03, 2014