Advertisement
Galebickosikasa

Untitled

Dec 23rd, 2021
977
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdbool.h>
  3. #include <string.h>
  4. #include <stdlib.h>
  5.  
  6. struct trie {
  7.     struct trie* a[26];
  8.     bool term;
  9. };
  10.  
  11. struct trie* init_trie (void) {
  12.     struct trie* t = malloc (sizeof (struct trie));
  13.     t->term = 0;
  14.     for (int i = 0; i < 26; ++i) t->a[i] = NULL;
  15.     return t;
  16. }
  17.  
  18. void add_word (struct trie* t, char* s, int i, int n) {
  19.     if (i == n) {
  20.         t->term = 1;
  21.         return;
  22.     }
  23.     int x = s[i] - 'a';
  24.     if (!t->a[x]) t->a[x] = init_trie ();
  25.     add_word (t->a[x], s, i + 1, n);
  26. }
  27.  
  28. void print_trie (struct trie* t) {
  29.     for (int i = 0; i < 26; ++i) {
  30.         if (t->a[i]) {
  31.             printf ("->%c\n", 'a' + i);
  32.             print_trie (t->a[i]);
  33.         }
  34.     }
  35.     printf ("<-\n");
  36. }
  37.  
  38. void destruct_trie (struct trie* t) {
  39.     for (int i = 0; i < 26; ++i) if (t->a[i]) destruct_trie (t->a[i]);
  40.     free (t);
  41. }
  42.  
  43. int main (void) {
  44.     struct trie* root = init_trie ();
  45.     char* s = malloc ((int)1e4);
  46.     int n;
  47.     scanf ("%d", &n);
  48.     for (int i = 0; i < n; ++i) {
  49.         scanf ("%s", s);
  50.         add_word (root, s, 0, strlen (s));
  51.     }
  52.     print_trie (root);
  53.     destruct_trie (root);
  54.  
  55.  
  56.  
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement