fork(2) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct trie
  4. {
  5.     char b[50];
  6.     int words;
  7.     struct trie *edges[30];
  8. };
  9. struct trie *root;
  10. struct trie *initialise(struct trie *node)
  11. {
  12.     int i;
  13.     node = (struct trie *)malloc(sizeof(struct trie));
  14.     node->b[0] = '\0';
  15.     node->words = 0;
  16.     for(i = 0; i < 30; i++) {
  17.         node->edges[i] = NULL;
  18.     }
  19.  
  20.     return node;
  21. }
  22. void addword(char s[],struct trie *temp)
  23. {
  24.     int i;
  25.     int k;
  26.  
  27.  
  28.     for(i = 0; i < strlen(s);i++) {
  29.         k = s[i] - 'a';
  30.         if(temp->edges[k] == NULL) {
  31.             temp->edges[k] = initialise(temp->edges[k]);
  32.         }
  33.         temp = temp->edges[k];
  34.     }
  35.     temp->words = 1;
  36.     strcpy(temp->b,s);
  37. }
  38. struct trie *findword(char s[],struct trie *temp)
  39. {
  40.     int i;
  41.     int k;
  42.  
  43.     for(i = 0; i < strlen(s); i++) {
  44.         k = s[i] - 'a';
  45.         if(temp->edges[k] == NULL) {
  46.             return NULL;
  47.         }
  48.         temp = temp->edges[k];
  49.     }
  50.  
  51.     return temp;
  52. }
  53.  
  54. int bfs(struct trie *node,char s[])
  55. {
  56.     queue<struct trie *> q;
  57.     struct trie *temp;
  58.     temp = initialise(temp);
  59.     int i;
  60.     int count;
  61.     count = 0;
  62.  
  63.     q.push(node);
  64.  
  65.     while(!q.empty()) {
  66.         temp = q.front();
  67.         //cout << "hi " << temp->b << endl;
  68.         if(temp->words == 1 && strcmp(temp->b,s) != 0) {
  69.             printf("%s\n",temp->b);
  70.             count++;
  71.         }
  72.         q.pop();
  73.  
  74.         for(i = 0; i < 26; i++) {
  75.             if(temp->edges[i] != NULL) {
  76.                 q.push(temp->edges[i]);
  77.             }
  78.         }
  79.     }
  80.  
  81.     return count;
  82.  
  83. }
  84. int main()
  85. {
  86.    int i;
  87.     char s[50];
  88.     char a[50];
  89.    int n;
  90.    int k;
  91.    root = initialise(root);
  92.    struct trie *temp;
  93.    temp = initialise(temp);
  94.  
  95.    scanf("%d",&n);
  96.    for(i = 0; i < n; i++) {
  97.         scanf("%s",s);
  98.         addword(s,root);
  99.    }
  100.    int j;
  101.  
  102.    scanf("%d",&k);
  103.    for(i = 1; i <= k; i++) {
  104.         scanf("%s",a);
  105.         printf("Case #%d:\n",i);
  106.         temp = findword(a,root);
  107.         if(temp == NULL) {
  108.             printf("No match.\n");
  109.         }
  110.         else {
  111.             //cout << "bfs " << temp->b << endl;
  112.            int count =  bfs(temp,a);
  113.            if(count == 0) {
  114.                printf("No match.\n");
  115.            }
  116.  
  117.         }
  118.  
  119.    }
  120.  
  121.    return 0;
  122.  
  123.  
  124.  
  125.  
  126.  
  127. }
  128.  
Runtime error #stdin #stdout 0s 3276KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/BsYhbb
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!