fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MAX_BITS 32
  5.  
  6. // Trie node structure
  7. typedef struct TrieNode {
  8.   struct TrieNode *children[2]; // Left (0) and Right (1)
  9.   int match;
  10.   int prefix_length;
  11. } TrieNode;
  12.  
  13. // Root of the Trie
  14. TrieNode *root;
  15.  
  16. // Convert an IP address to a 32-bit integer
  17. unsigned int ip(int a, int b, int c, int d) {
  18.   return (a << 24) | (b << 16) | (c << 8) | d;
  19. }
  20.  
  21. // Create a new Trie node
  22. TrieNode *newTrieNode() {
  23.   TrieNode *node = (TrieNode *)malloc(sizeof(TrieNode));
  24.   node->children[0] = node->children[1] = NULL;
  25.   node->match = -1;         // Default match value
  26.   node->prefix_length = -1; // No prefix set initially
  27.   return node;
  28. }
  29.  
  30. // Insert subnet into the Trie
  31. void insertSubnet(int a, int b, int c, int d, int bits, int match) {
  32.   unsigned int subnet = ip(a, b, c, d);
  33.   TrieNode *current = root;
  34.  
  35.   for (int i = 31; i >= 32 - bits; i--) {
  36.     int bit = (subnet >> i) & 1; // Extract i-th bit
  37.     if (!current->children[bit]) {
  38.       current->children[bit] = newTrieNode();
  39.     }
  40.     current = current->children[bit];
  41.   }
  42.   // Store the match value and prefix length
  43.   current->match = match;
  44.   current->prefix_length = bits;
  45. }
  46.  
  47. // Search for the best match for a given IP
  48. int searchIP(int a, int b, int c, int d) {
  49.   unsigned int target = ip(a, b, c, d);
  50.   TrieNode *current = root;
  51.  
  52.   int best_match = -1;
  53.   int longest_prefix = -1;
  54.  
  55.   for (int i = 31; i >= 0; i--) {
  56.     int bit = (target >> i) & 1;
  57.     if (!current->children[bit]) {
  58.       break; // No more matching bits
  59.     }
  60.     current = current->children[bit];
  61.     if (current->prefix_length != -1) { // Valid match found
  62.       best_match = current->match;
  63.       longest_prefix = current->prefix_length;
  64.     }
  65.   }
  66.  
  67.   return best_match;
  68. }
  69.  
  70. // Free Trie memory
  71. void freeTrie(TrieNode *node) {
  72.   if (!node)
  73.     return;
  74.   freeTrie(node->children[0]);
  75.   freeTrie(node->children[1]);
  76.   free(node);
  77. }
  78.  
  79. int main() {
  80.   int n, m;
  81.   scanf("%d", &n);
  82.  
  83.   root = newTrieNode(); // Initialize Trie root
  84.  
  85.   // Read and insert subnets into the Trie
  86.   for (int i = 0; i < n; i++) {
  87.     int a, b, c, d, bits, match;
  88.     scanf("%d.%d.%d.%d/%d %d", &a, &b, &c, &d, &bits, &match);
  89.     insertSubnet(a, b, c, d, bits, match);
  90.   }
  91.  
  92.   // Read and process IPs
  93.   scanf("%d", &m);
  94.   for (int i = 0; i < m; i++) {
  95.     int a, b, c, d;
  96.     scanf("%d.%d.%d.%d", &a, &b, &c, &d);
  97.     printf("%d\n", searchIP(a, b, c, d));
  98.   }
  99.  
  100.   freeTrie(root); // Free memory
  101.   return 0;
  102. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4
192.168.1.0/24 0
10.0.0.0/8 1
172.16.0.0/16 2
192.168.0.0/16 3
3
192.168.1.128
192.168.0.255
10.255.255.254
stdout
copy 
0
3
1
https://ideone.com/hxYRXe
language:
C (gcc 8.3)
created:
10 days 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!