SHARE
TWEET

Untitled

a guest Jan 21st, 2020 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #define size 26
  3. struct elem {
  4.     char ** v;
  5.     struct elem ** array;
  6.     struct elem * parent;
  7.     int count;
  8. };
  9. struct  elem * Init(struct elem * parent) {
  10.     struct elem * a = (struct elem *)malloc(sizeof(struct elem));
  11.     a->v = NULL;
  12.     a->parent = parent;
  13.     a->count  = 0;
  14.     a->array = (struct elem**)malloc(size*sizeof(struct elem*));
  15.     for(int i = 0;i < size;i++) {
  16.         a->array[i] = NULL;
  17.     }
  18.     return a;
  19. }
  20. void Insert(struct elem * root,char * v) {
  21.     struct elem * a = root;
  22.     int length = strlen(v), i =0;
  23.     while(i < length) {
  24.         a->count++;
  25.         struct elem * b = a->array[v[i] - 'a'];
  26.         if (b == NULL) {
  27.             break;
  28.         }
  29.         a = b;
  30.         i++;
  31.     }
  32.     if ((a->v != NULL) && (i == length)) {
  33.         a->v = &v;
  34.         i--;
  35.         while(i > 0) {
  36.             a->count--;
  37.             struct elem * b = a->parent;
  38.             if (b == NULL) {
  39.                 break;
  40.             }
  41.             a = b;
  42.             i--;
  43.         }
  44.     }
  45.     else {
  46.         if (i == length) {
  47.             a->count++;
  48.         }
  49.         for(int j = i;j < length;j++) {
  50.             a->array[v[j]-'a'] = Init(a);
  51.             a = a->array[v[j]-'a'];
  52.             a->count++;
  53.         }
  54.         a->v = &v;
  55.     }
  56. }
  57. int Prefix(struct elem * root,char * v) {
  58.     struct elem * a = root;
  59.     int length = strlen(v),sum = 0,i = 0;
  60.     while(i < length) {
  61.         struct elem * b = a->array[v[i] - 'a'];
  62.         if (b == NULL) {
  63.             break;
  64.         }
  65.         a = b;
  66.         i++;
  67.     }
  68.     if (i != length) {
  69.         return 0;
  70.     }
  71.     else {
  72.         return a->count;
  73.     }
  74.    
  75. }
  76. void Delete(struct elem * root,char * v) {
  77.     struct elem * a = root;
  78.     int i = 0,length  = strlen(v);
  79.     while(i < length) {
  80.         a->count--;
  81.         struct elem * b = a->array[v[i] - 'a'];
  82.         if (b == NULL) {
  83.             break;
  84.         }
  85.         a = b;
  86.         i++;
  87.     }
  88.     a->count--;
  89.     a->v = NULL;
  90. }
  91. void freebor(struct elem * elem) {
  92.     if (elem == NULL) ;
  93.     else  {
  94.         for(int i = 0;i < size;i++) {
  95.             if (elem->array[i] != NULL) {
  96.                 freebor(elem->array[i]);
  97.             }
  98.         }
  99.         free(elem->array);
  100.         free(elem);
  101.     }
  102. }
  103. int main()
  104. {
  105.     char name[10];
  106.     char v[100000];
  107.     int n;
  108.     scanf("%d" , &n);
  109.     struct elem * root = (struct elem *)malloc(sizeof(struct elem));
  110.     root->parent = NULL;
  111.     root->count  = 0;
  112.     root->v = NULL;
  113.     root->array = (struct elem**)malloc(size*sizeof(struct elem*));
  114.     for(int i = 0;i < size;i++) {
  115.         root->array[i] = NULL;
  116.     }
  117.     for(int i = 0;i < n;i++) {
  118.         scanf("%s%s" , name , v);
  119.         if ((strcmp(name,"INSERT")) == 0) Insert(root,v);
  120.         else {
  121.             if ((strcmp(name,"DELETE")) == 0) Delete(root,v);
  122.             else printf("%d\n" , Prefix(root,v));
  123.         }
  124.     }
  125.     freebor(root);
  126.     return 0;
  127. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top