I recently had to work on this problem, and needed a fast implementation.

I found the easiest and fastest way was to use a Trie as mentioned by rg0now.

I used the random generator which BrowserUk supplied to generate the random dataset.

My version processed the dataset in less than two seconds on my 3.8GHz Linux box.

I don't have nice sorted output though. It should be trivial to build up a data structure as you go if you need sorted output...

Here's the code:

#! /usr/bin/env perl

use strict;
use warnings;
use autodie;
use 5.10.0;

use Tree::Trie;
use Net::IP qw(ip_splitprefix ip_iptobin ip_get_mask);

my $trie = Tree::Trie->new();

while (<>) {
    chomp;
    my ($ip, $len) = ip_splitprefix($_);

    my $binip = ip_iptobin($_,4);

    my $trie_entry = substr($binip, 0, $len);

    $trie->deepsearch('prefix');
    my $data = $trie->lookup_data($trie_entry);

    if ($data) {
        say "'$_' is contained by or equals '$data'";
    }
    else {
        $trie->deepsearch('choose');
        my $data = $trie->lookup_data($trie_entry);

        if ($data) {
            say "'$_' contains '$data'";
        }
    }
    $trie->add_data($trie_entry, $_);
}
[download]

Some truncated sample output:

time ./trie_overlap.pl <50k_ips

...

'116.15.84.0/23' is contained by or equals '116.14.0.0/15'
'108.245.172.0/24' is contained by or equals '108.244.0.0/14'
'13.238.173.128/25' is contained by or equals '13.224.0.0/11'
'37.179.224.0/19' is contained by or equals '37.179.192.0/18'
'73.147.0.0/17' is contained by or equals '73.144.0.0/12'
'150.152.0.0/13' contains '150.154.0.0/18'
'171.93.16.0/22' is contained by or equals '171.0.0.0/9'
'80.246.128.0/21' is contained by or equals '80.240.0.0/13'

real    0m1.957s
user    0m1.832s
sys     0m0.124s
[download]

Anyone see any issues with this? It hasn't been completely battle tested yet :)

Best,

Jim