路由表最长匹配

in Algorithm Pageviews

solve actually problem!

路由表最长匹配是 IPV4 路由最基本的功能之一，当路由器收到一个数据包时，会将数据包的目的IP地址与本地路由表进行匹配：

  • 格式：目的IP地址为dstIp，路由表中每条路由为 entryIp/m ，m 表示掩码长度，如10.11.22.0/23，所有IP用点分十进制表示

  • 匹配方式

    • 如果entryIp 和 dstIp 的二进制表示的前m个bit相同，就说明与这条路由是匹配的。10.11.22.0 的二进制表示如下：

        |---------------------------------------------------------------|
  |0|1|2|3|4|5|6|7|0|1|2|3|4|5|6|7|0|1|2|3|4|5|6|7|0|1|2|3|4|5|6|7|
  |---------------------------------------------------------------|
  |0 0 0 0 1 1 0 0|0 0 0 0 1 1 0 1|0 0 0 1 0 1 1 0|0 0 0 0 0 0 0 0|
  |---------------------------------------------------------------|

    • 0.0.0.0/0 是默认路由，它与任何目的的IP地址都是匹配的，m值为0。

    • 所有匹配的路由中，m 最大的即为“最长匹配”

现在给定目的 IP 地址 dstIp 和本地路由表ipTable，请输出最长匹配的路由，如果有多条，则按照给出的先后顺序输出最前面的，如果找不到，就输出字符串empty。

样例

输入：

"192.168.0.3"

["10.166.50.0/23","192.0.0.0/8","10.255.255.255/32","192.168.0.1/24","127.0.0.0/8","192.168.0.0/24"]

输出：

“192.168.0.1/24”

代码实现如下:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    string RouterSearch(const string &dstIp, const vector<string> &ipTable)
    {
        auto dstIpInt = ParseIpNumber(dstIp);
        vector<int> dstFullInfo(32);
        ComBinary32NumIp(dstIpInt, dstFullInfo);
        for (size_t i = 0; i < ipTable.size(); i++) {
            auto routeIpInt = ParseIpNumber(ipTable[i]);
            vector<int> routeFullInfo(32);
            ComBinary32NumIp(routeIpInt, routeFullInfo);
            int mask = routeIpInt[routeIpInt.size() - 1];
            bool isMatch = CheckMatch(routeFullInfo, dstFullInfo);
            if (ipTable[i] == "0.0.0.0/0") {
                isMatch = true;
            }
            
            if (match && (maxLength < mask)) {
                maxLength = mask;
                maxMatchStr = ipTable[i];
            }
        }
        return maxMatchStr;
    }

    vector<int> ParseIpNumber(const string &ipStr)
    {
        vector<int> result;
        int start = 0;
        int end = 0;
        int ipNum = 0;
        while (end < ipStr.size()) {
            if (ipStr[end] == '.' || ipStr[end] == '/') {
                ipNum = stoi(ipStr.substr(start, end - start));
                result.push_back(ipNum);
                start = end + 1;
            }
            end++;
        }
        
        ipNum = stoi(ipStr.substr(start));
        result.push_back(ipNum);
        return result;
    }
    
    vector<int> ParseDecToBinary(int ipByte)
    {
        vector<int> binaryNum(8);
        int originNum = ipByte;
        int i = 7;
        while (originNum != 0) {
            binaryNum[i] = originNum % 2;
            originNum /= 2;
            i--;
        }
        return binaryNum;
    }
    
    void ComBinary32NumIp(const vector<int> &ipVec, vector<int> &binaryNum)
    {
        auto pos = 0;
        for (auto i = 0; i < 4; i++) {
            vector<int> currIpByte = ParseDecToBinary(ipVec[i]);
            for (auto j = 0; j < 8; j++) {
                binaryNum[pos++] = currIpByte[j];
            }
        }
    }
    
    bool CheckMatch(vector<int> routeInfo, vector<int> &dstIpInfo, int m)
    {
        bool match = true;
        for (int i = 0; i < m; i++) {
            if (routeInfo[i] != dstIpInfo[i]) {
                match = false;
                break;
            }
        }
        return match;
    }

private:
    int maxLength = INT_MIN;
    string maxMatchStr = "empty";
};