题目的主要信息：

• 子网掩码与IP地址结构相同，是32位二进制数，其中网络号部分全为“1”和主机号部分全为“0”
• 若两台主机的IP地址分别与它们的子网掩码相“位与”后的结果相同，则说明这两台主机在同一子网中
• 根据输入的子网掩码和两个IP地址，判断输入是否合法（非法输出1），判断两个IP地址是否属于同一个子网（是输出0，否输出2）
•  掩码与IP每一段在 0 - 255 之间，掩码不能为全1全0，且全部1在前，全部0在后半部分

方法一：暴力模拟

具体做法：

我们对于输入的三个地址，先判断合法性，再验证两个IP地址是否属于同一个子网。

验证合法性的时候，我们遍历该字符串，用长度为4的数组记录数字，并用变量统计遇到的点的个数，点数不能超过3，否则不合法，遇到除了点和数字以外的字符也是非法，遇到数字字符则组装成数字，遇到点之后检查它前一个组成的数字是否在0-255之间，不在也不合法。

在判断的过程我们也要计算这个IP地址转化而成的32位长整数是什么，这里我们用unsigned int，因为用int会多出符号位而少一位可以用的导致超出变量表示范围。经过上面的判断，我们得到了四个整数，我们可以将第0个整数左移24位，使其成为32位二进制的头8个，然后第1个整数左移16位，第2个整数左移8位，最后一个不变，四个数通过位或操作即可组装在一起。

然后就是判断子网掩码是否是先1后0的格式，我们每次将掩码最后一位与1做位与运算，如果为1则继续，然后右移去掉最后一位，找到第一次出现1以后，我们标记，在有标记的情况下又出现了0，说明0与1混出现了，不合法，这样遍历32次，将每一位查看一遍就行了。要注意全0和全1情况也是不允许的。

都合法的情况下，我们再将刚刚得到的长整数两个IP地址分别与掩码做位与运算，相同则同一个子网，否则不同子网。

#include<iostream>
#include<string>
using namespace std;

bool isLegal(string s, unsigned int& binum){ //检查掩码或者IP地址的数字部分是否合法，并将合法的转换为长整数
    int point = 0; //统计点的个数
    unsigned int num[4] = {0, 0, 0, 0}; //记录四个数字
    for(int i = 0; i < s.length(); i++){
        if(point > 3) //超过3个点，四个数字不合法
            return false;
        if(s[i] != '.'){
            if (s[i] < '0' || s[i] > '9')  //非数字不合法
                return false;
            num[point] = num[point] * 10 + s[i] - '0'; //转化数字
        }else{
            if(num[point] > 255 || num[point] < 0) //数字在0-255
                return false; 
            point++; //统计点的个数
        }
    }
    if (num[3] > 255 || num[3] < 0) 
		return false;
    binum = num[0] << 24 | num[1] << 16 | num[2] << 8 | num[3]; //位运算组装
    return true;
}

bool isMask(unsigned int mask){ //单独检查掩码是否是先1后0
    if(mask & 1)
        return false; //掩码最后一位不可能是1
    bool flag = false; //掩码逆序1第一次出现标记为true
    for(int i = 1; i < 32; i++){
        mask >>= 1; //每次右移一位
        if((mask & 1) && (!flag)){ //第一次出现1
            flag = true;
        }else if(((mask & 1) == 0) && (flag)){ //已经出现过1的情况下出现0不合法
            return false;
        }
    }
    if(!flag) //mask全0
        return false;
    return true;
}
int main(){
    string mask, ip1, ip2;
    while(cin >> mask >> ip1 >> ip2){
        unsigned int bi_mask = 0;
        unsigned int bi_ip1 = 0;
        unsigned int bi_ip2 = 0;
        //判断是否合法
        if(!isLegal(mask, bi_mask) || !isLegal(ip1, bi_ip1) || !isLegal(ip2, bi_ip2) || !isMask(bi_mask)){
            cout << 1 << endl;
            continue;
        }
        if((bi_mask & bi_ip1) == (bi_mask & bi_ip2)) //比较是否同一个子网
            cout << 0 << endl;
        else
            cout << 2 << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为输入的地址字符串长度，合法情况下都是常数时间，不合法情况下遍历字符串需要$O(n)O(n)$
• 空间复杂度：$O(1)O(1)$，常数空间

方法二：字符串流输入输出+正则表达式

具体做法：

对于类似IP地址的字符串格式，我们可以使用字符串流输入输出，来获取数字，而不需要遍历字符串然后拆分，我们只需要在流输出的时候用一个char型变量接收那个点即可。然后遍历得到的每个数字，依次检查是否合法范围内，再将其转化成长整数。

这里流输出就默认了最后一个数后面没有其他字符了，正好题目中也没有这种案例。

对于掩码我们也可以用正则表达式直接匹配，而不用移位找有没有01混在一起。

#include<iostream>
#include<string>
#include<sstream>
#include<regex>
using namespace std;

bool isLegal(string s, unsigned int& binum){ //检查掩码或者IP地址的数字部分是否合法，并将合法的转换为长整数
    int point = 0; //统计点的个数
    unsigned int num[4] = {0, 0, 0, 0}; //记录四个数字
    stringstream ss;
    ss << s;
    char c;
    ss >> num[0] >> c >> num[1] >> c >> num[2] >> c >> num[3]; //直接用字符串流输出数字中间的点用字符变量接受
    for(int i = 0; i < 4; i++){ //检查数字是否合法
        if(num[i] < 0 || num[i] > 255)
            return false;
    }
    binum = num[0] << 24 | num[1] << 16 | num[2] << 8 | num[3]; //位运算组装
    return true;
}

bool isMask(string mask){ //单独检查掩码是否是先1后0
    if(mask == "0.0.0.0" || mask == "255.255.255.255") //全0全1不合法
        return false;
    string re = "^((0|128|192|224|240|248|252|254)\.0\.0\.0|255\.(0|128|192|224|240|248|252|254)\.0\.0|255\.255\.(0|128|192|224|240|248|252|254)\.0|255\.255\.255\.(0|128|192|224|240|248|252|254|255))$";
    regex pattern(re);
    if(regex_match(mask, pattern)) //正则表达式匹配正确的掩码
        return true;
    else
        return false;
}
int main(){
    string mask, ip1, ip2;
    while(cin >> mask >> ip1 >> ip2){
        unsigned int bi_mask = 0;
        unsigned int bi_ip1 = 0;
        unsigned int bi_ip2 = 0;
        //判断是否合法
        if(!isLegal(mask, bi_mask) || !isLegal(ip1, bi_ip1) || !isLegal(ip2, bi_ip2) || !isMask(mask)){
            cout << 1 << endl;
            continue;
        }
        if((bi_mask & bi_ip1) == (bi_mask & bi_ip2)) //比较是否同一个子网
            cout << 0 << endl;
        else
            cout << 2 << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(1)O(1)$，流输入和输出及正则匹配都是常数时间
• 空间复杂度：$O(1)O(1)$，常数空间