cp-algorithms/trie.cpp at master · x-coderx/cp-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>
using namespace std;
struct trie
{
    bool eow;
    trie * all[26];
};
trie* getNode()
{
    trie* temp = new trie;
    temp->eow =false;
    for(int i=0;i<26;i++)
        temp->all[i]=NULL;
    return temp;
}
void insert(trie *root, string s)
{
    for(int i=0;i<s.length();i++)
    {
        if(root->all[s[i]-'a'])
        {
            root=root->all[s[i]-'a'];
        }
        else
        {
            root->all[s[i]-'a'] = getNode();
            root=root->all[s[i]-'a'];
        }
        if(i==s.length()-1)
                root->eow=true;
    }
    return;
}
void print(trie*root,string s)
{
    if(root->eow)
    {
        cout<<s<<endl;
    }
    for(int i=0;i<26;i++)
    {
        if(root->all[i])
        {
            print(root->all[i],s+(char)(i+'a'));
        }
    }
    return;
}
bool searchTrie(trie* root, string s)
{
    for(int i=0;i<s.length();i++)
    {
        if(root->all[s[i]-'a']==NULL)
            return false;
        else
            root=root->all[s[i]-'a'];
    }
    if(root->eow)
        return true;
    return false;
}
void deleteTrie(trie* root,string s)
{
    if(searchTrie(root,s)==false)
        return;

}
using namespace std;
int main()
{
    string b,e;
    cin>>b>>e;
    int n;
    cin>>n;
    string s[n];
    trie * root = new trie();
    insert(root,b);
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
        insert(root,s[i]);
    }
    insert(root,e);
    print(root,"");
    cout<<searchTrie(root,"ank")<<endl;
    cout<<searchTrie(root,"malik");
    return 0;
}