Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- struct Tree {
- struct List* list;
- int x;
- };
- struct ListNode {
- struct Tree* tree;
- struct ListNode* next;
- };
- struct List {
- struct ListNode* begin;
- struct ListNode* end;
- int size;
- };
- struct List* init_list (void) {
- struct List* list = malloc (sizeof (struct List));
- list->begin = list->end = NULL;
- list->size = 0;
- return list;
- }
- struct Tree* init_tree (int x) {
- struct Tree* tree = malloc (sizeof (struct Tree));
- tree->x = x;
- tree->list = init_list();
- return tree;
- }
- struct ListNode* init_node (int x) {
- struct ListNode* node = malloc (sizeof (struct ListNode));
- node->tree = init_tree(x);
- node->next = NULL;
- return node;
- }
- void push_list (struct Tree* tree, int x) {
- struct List* list = tree->list;
- struct ListNode* node = init_node(x);
- if (list->size == 0) {
- list->begin = list->end = node;
- } else {
- list->end->next = node;
- list->end = node;
- }
- ++list->size;
- }
- void destruct_tree (struct Tree* tree);
- void destruct_list (struct List* list) {
- struct ListNode* node = list->begin;
- while (node) {
- destruct_tree(node->tree);
- struct ListNode* node_next = node->next;
- free (node);
- node = node_next;
- }
- free (list);
- }
- void destruct_tree (struct Tree* tree) {
- if (!tree) return;
- struct List* list = tree->list;
- destruct_list(list);
- free (tree);
- }
- struct Tree* find_tree (struct List* list, int x) {
- if (list->size == 0) return NULL;
- struct ListNode* node = list->begin;
- while (node) {
- if (node->tree->x == x) return node->tree;
- node = node->next;
- }
- return NULL;
- }
- void add_word (struct Tree* tree, char* s, int i, int n) {
- if (i == n) return;
- int x = s[i] - 'a';
- struct Tree* tree1 = find_tree(tree->list, x);
- if (!tree1) {
- push_list(tree, x);
- tree1 = find_tree(tree->list, x);
- if (!tree1) {
- printf ("no Tree\n");
- exit (0);
- }
- }
- add_word (tree1, s, i + 1, n);
- }
- int calc (struct Tree* tree) {
- if (!tree) return 0;
- int ans = 1;
- for (int i = 0; i < 26; ++i) {
- struct Tree* tree1 = find_tree(tree->list, i);
- if (tree1) ans += calc (tree1);
- }
- return ans;
- }
- int main(void) {
- char* s = malloc (2020);
- scanf ("%s", s);
- struct Tree* root = init_tree(-1);
- int n = (int)strlen (s);
- for (int i = 0; i < n; ++i) {
- add_word(root, s, i, n);
- }
- printf ("%d\n", calc (root));
- free (s);
- destruct_tree(root);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement