Advertisement
Galebickosikasa

Untitled

Dec 25th, 2021
1,241
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.69 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. struct Tree {
  6.     struct List* list;
  7.     int x;
  8. };
  9.  
  10. struct ListNode {
  11.     struct Tree* tree;
  12.     struct ListNode* next;
  13. };
  14.  
  15. struct List {
  16.     struct ListNode* begin;
  17.     struct ListNode* end;
  18.     int size;
  19. };
  20.  
  21. struct List* init_list (void) {
  22.     struct List* list = malloc (sizeof (struct List));
  23.     list->begin = list->end = NULL;
  24.     list->size = 0;
  25.     return list;
  26. }
  27.  
  28. struct Tree* init_tree (int x) {
  29.     struct Tree* tree = malloc (sizeof (struct Tree));
  30.     tree->x = x;
  31.     tree->list = init_list();
  32.     return tree;
  33. }
  34.  
  35. struct ListNode* init_node (int x) {
  36.     struct ListNode* node = malloc (sizeof (struct ListNode));
  37.     node->tree = init_tree(x);
  38.     node->next = NULL;
  39.     return node;
  40. }
  41.  
  42. void push_list (struct Tree* tree, int x) {
  43.     struct List* list = tree->list;
  44.     struct ListNode* node = init_node(x);
  45.     if (list->size == 0) {
  46.         list->begin = list->end = node;
  47.     } else {
  48.         list->end->next = node;
  49.         list->end = node;
  50.     }
  51.     ++list->size;
  52. }
  53.  
  54. void destruct_tree (struct Tree* tree);
  55.  
  56. void destruct_list (struct List* list) {
  57.     struct ListNode* node = list->begin;
  58.     while (node) {
  59.         destruct_tree(node->tree);
  60.         struct ListNode* node_next = node->next;
  61.         free (node);
  62.         node = node_next;
  63.     }
  64.     free (list);
  65. }
  66.  
  67. void destruct_tree (struct Tree* tree) {
  68.     if (!tree) return;
  69.     struct List* list = tree->list;
  70.     destruct_list(list);
  71.     free (tree);
  72. }
  73.  
  74. struct Tree* find_tree (struct List* list, int x) {
  75.     if (list->size == 0) return NULL;
  76.     struct ListNode* node = list->begin;
  77.     while (node) {
  78.         if (node->tree->x == x) return node->tree;
  79.         node = node->next;
  80.     }
  81.     return NULL;
  82. }
  83.  
  84. void add_word (struct Tree* tree, char* s, int i, int n) {
  85.     if (i == n) return;
  86.     int x = s[i] - 'a';
  87.     struct Tree* tree1 = find_tree(tree->list, x);
  88.     if (!tree1) {
  89.         push_list(tree, x);
  90.         tree1 = find_tree(tree->list, x);
  91.         if (!tree1) {
  92.             printf ("no Tree\n");
  93.             exit (0);
  94.         }
  95.     }
  96.     add_word (tree1, s, i + 1, n);
  97. }
  98.  
  99. int calc (struct Tree* tree) {
  100.     if (!tree) return 0;
  101.     int ans = 1;
  102.     for (int i = 0; i < 26; ++i) {
  103.         struct Tree* tree1 = find_tree(tree->list, i);
  104.         if (tree1) ans += calc (tree1);
  105.     }
  106.     return ans;
  107. }
  108.  
  109. int main(void) {
  110.     char* s = malloc (2020);
  111.     scanf ("%s", s);
  112.     struct Tree* root = init_tree(-1);
  113.     int n = (int)strlen (s);
  114.     for (int i = 0; i < n; ++i) {
  115.         add_word(root, s, i, n);
  116.     }
  117.     printf ("%d\n", calc (root));
  118.     free (s);
  119.     destruct_tree(root);
  120.  
  121.  
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement