B.Tech students going to make their own higher studies application! The application must perform two types of operations:
add a name, where name is a string denoting a Student name. This must store the name as a new Studentin the application.
find partial, where partial is a string denoting a partial name to search the application for. It must count the number of Students starting with partial and print the count on a new line.
Given n sequential add and find operations, perform each operation in order.
It is guaranteed that name and partial contain lowercase English letters only.
The input doesn't have any duplicate name for the add operation.
Input:
The first line contains a single integer, n, denoting the number of operations to perform.
Each line i of the n subsequent lines contain an operation in one of the two forms defined above.
Output:
For each finds partial operation, print the number of Students' names starting with partial on a new line.#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct node
{
bool isEOW;
int count;
struct node *letters[26];
}Trie;
void h(){
printf("struct Node* children[26];");
}
Trie *createNode()
{
int i;
Trie *temp=malloc(sizeof(Trie));
temp->isEOW=false;
temp->count=0;
for(i=0; i<26; i++)
{
temp->letters[i]=NULL;
}
return temp;
}
Trie *insert(Trie *root,char *name)
{
int i;
Trie *temp=root;
for(i=0; name[i]!='\0'; i++)
{
if(root->letters[name[i]-'a']==NULL)
root->letters[name[i]-'a']=createNode();
root=root->letters[name[i]-'a'];
root->count++;
}
root->isEOW=true;
return temp;
}
int main()
{
int i;
long n;
Trie* root=createNode();
scanf("%ld",&n);
char a[5],name[22];
while(n--)
{
scanf("%s",a);
scanf(" %s",name);
if(strcmp(a,"add")==0)
root= insert(root,name);
else if(strcmp(a,"find")==0)
{
Trie *temp=root;
for(i=0; i<strlen(name); i++)
{
temp=temp->letters[name[i]-'a'];
if(!temp)
{
printf("0\n");
break;
}
}
if(i==strlen(name))
printf("%d\n",temp->count);
}
}
return 0;
}
INPUT_1:
4
add kick
add kickman
find kic
find kan
OUTPUT:
2
0
INPUT_2:
4
add jac
add jackran
find jac
find ran
OUTPUT:
2
0