CIDR合并

CIDR合并

如何判斷包含關係

把需要截取的部分用&運算獲取出來

然後判斷相同位置截取的結果是否相同，相同就是有包含關係

最後一個元素：ans[ans.end()-1]

#include <iostream>
#include <algorithm>
using namespace std;
string s;
int n;
#include <vector>
struct IP
{
    int A[4];
    int len;
} A[1000005];
bool cmp(IP a, IP b)
{
    for (int i = 0; i < 4; i++)
    {
        if (a.A[i] != b.A[i])
            return a.A[i] < b.A[i];
    }
    return a.len < b.len;
}
void init(int x)
{
    int len = s.length();
    int tmp[4];
    int j = 0;
    int o = 0;
    bool f = 0;
    for (int i = 0; i < len; i++)
    {
        if (s[i] == '.')
        {
            tmp[j++] = o;
            o = 0;
        }
        else if (s[i] == '/')
        {
            tmp[j++] = o;
            while (j < 4)
            {
                tmp[j++] = 0;
            }
            f = 1;
            o = 0;
        }
        else
        {
            o = o * 10 + s[i] - '0';
        }
    }
    if (f)
    {
        len = o;
    }
    else
    {
        tmp[j++] = o;
        if (j == 1)
            len = 8;
        else if (j == 2)
            len = 16;
        else if (j == 3)
            len = 24;
        else
            len = 32;
        while (j < 4)
        {
            tmp[j++] = 0;
        }
    }
    for (int i = 0; i < 4; i++)
    {
        A[x].A[i] = tmp[i];
    }
    A[x].len = len;
}
int E[]={128,192,224,240,248,252,254,255};
bool contain(IP x, IP y)
{
    if (x.len > y.len)
        return false;
    int n = x.len;
    int j = 0;
    while (n > 0)
    {
        if (n >= 8)
        {
            if (((x.A[j] & 255) ^(y.A[j]&255))!=0)
                return false;
        }
        if (((x.A[j] & E[n-1]) ^(y.A[j]&E[n-1]))!=0)
            return false;
        n -= 8;
        j++;
    }
    return true;
}
vector<IP> v;
vector<IP> ans;
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        init(i);
    }
    sort(A, A + n, cmp);
    int j = 1;
    for (int i = 0; i < n; i++)
    {
        j = i + 1;
        v.push_back(A[i]);
        while (j < n && contain(A[i], A[j]))
        {
            j++;
        }
        i = j - 1;
    }
    n = v.size();
    j = 0;
    for (int i = 0; i < n; i++)
    {
        if (i == 0)
            ans.push_back(v[0]);
        else
        {
            IP b = ans[ans.size() - 1];
            if (b.len == v[i].len)
            {
                 j = 0;
                IP c;
                c.len = b.len - 1;
                int len = c.len;

                while (len > 0)
                {
                    if (len >= 8)
                    {
                        c.A[j] = b.A[j];
                    }
                    c.A[j] = (b.A[j] & E[len-1]);
                    len -= 8;
                    j++;
                }
                while (j < 4)
                    c.A[j++] = 0;
                if (contain(c, v[i]))
                {
                    v[i] = c;
                    ans.erase(ans.end()-1);
                    if(!ans.empty())
                    i--;
                    else ans.push_back(v[i]);

                }
                else
                {
                    ans.push_back(v[i]);
                }
            }
            else
            {
                ans.push_back(v[i]);
            }
        }
    }
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i].A[0] << '.' << ans[i].A[1] << '.' << ans[i].A[2] << '.' << ans[i].A[3] << '/' << ans[i].len << '\n';
    }
}
/*
2
10/9
10.128/9
*/