一、题目
路由表最长匹配:将目标IP地址dstIP与路由为entryIP/掩码长度m(比如10.166.50.0/23)进行匹配,找出匹配掩码m最长值。
匹配规则:
如果dstIP和entryIP的二进制表示的前m个位相同,则说明是匹配的。
0.0.0.0是默认路由,与任何dstIP均匹配,m值为0。
所有匹配的路由中,m的最大值即为“最长匹配”。
二、样例
第一行是dstIP
第二行是总entryIP数
第三行之后是具体的entryIP/m
192.168.0.3
6
10.166.50.0/23
192.0.0.0/0
10.255.255.255/32
192.168.0.1/24
127.0.0.0/0
192.168.0.0.0/24
输出
192.168.0.1/24
三、代码实现
// ipTable是个二维数组,每一个数组中第0列存IP,第1列存掩码
private static String routeSearch(String dstIp, String[][] ipTable) {
String dstIpBinary = getRoute(dstIp);
LinkedList<String> maxMatchList = new LinkedList<>();
int maxMatch = -1;
for (String[] strings : ipTable) {
String tempRoute = strings[0];
int maxNum = Integer.parseInt(strings[1]);
if (tempRoute.equals("0.0.0.0") && maxNum == 0) {
maxMatch = maxNum;
maxMatchList.add(tempRoute + "/" + maxNum);
continue;
}
if (isMatch(dstIpBinary, getRoute(tempRoute), maxNum) && maxNum > maxMatch) {
maxMatchList.clear();
maxMatch = maxNum;
maxMatchList.add(tempRoute + "/" + maxNum);
}
}
if (maxMatchList.isEmpty()) {
return "empty";
}
return maxMatchList.getFirst();
}
// 判断在给定matchNum长度下,是否匹配
private static boolean isMatch(String src, String ds, int matchNum) {
for (int i = 0; i < matchNum; i++) {
if (src.charAt(i) != ds.charAt(i)) {
return false;
}
}
return true;
}
// 将IP地址转换成二进制
private static String getRoute(String s) {
String[] ipSplit = s.split("\\.");
StringBuilder stringBuilder = new StringBuilder();
for (String ip : ipSplit) {
// 转换成二进制,不足8位,则补0
String binaryString = Integer.toBinaryString(Integer.parseInt(ip));
String formatBinaryStr = String.format("%8s", binaryString);
formatBinaryStr = formatBinaryStr.replace(" ", "0");
stringBuilder.append(formatBinaryStr);
}
return stringBuilder.toString();
}