hiho一下第149周《403 Forbidden》题目分析

3
2

每个IP地址可以看作是一个长度32的01字符串。同理每个子网掩码(address/mask)可以看作一个长度不超过32的01字符串。

例如对于样例

allow 1.2.3.4/30
deny 1.1.1.1
allow 127.0.0.1
allow 123.234.12.23/3
deny 0.0.0.0/0

对应的01串为:

allow   00000001 00000010 00000011 000001
deny    00000001 00000001 00000001 00000001
allow   01111111 00000000 00000000 00000001
allow   011
deny                        (空串)

然后对于每一个要处理的IP,我们需要判断它是不是有一个前缀同某一个规则匹配。

例如IP1.2.3.4,它的01串是00000001 00000010 00000011 00000100,第一条规则恰好是它的前缀。所以1.2.3.4会匹配allow 1.2.3.4/30,会被允许访问。当然一个IP有可能同时匹配多条规则,比如1.2.3.4也会匹配到deny 0.0.0.0/0,这时按照题意以输入中靠前的规则为准。

对于这样的前缀匹配问题,我们当然首先会想到用trie树解决啦!

对于每一条规则,我们把它的01串插入到trie树中,同时在终结点记录这条规则是allow还是deny,以及规则的序号是多少。

对于每一条要处理的IP,我们在trie树中查找这个01串。沿途经过的终结点都是匹配上的规则。我们只需要在这些终结点中找到序号最小的规则即可。

总复杂度是O(32(N+M))的。

2 answer(s)

1

这道题目有个坑点....在于输入的allow和deny可能是相同的。 比如:

allow 192.168.1.0/24
deny 192.168.1.0/24

这个时候在构造Trie的时候,如果不进行维护,而直接添加,就会覆盖前面一次的结果,而题目要求第一次匹配,也就是说,只要某个点被确定是allow或者deny之后,后面所有需要再复写的request都可以忽略。

  • 题解里面已经说了找到序号最小的规则,意味着的遵守“最前”的规则了

  • 添加评论
  • reply
0

样例的最后一条测试用例219.142.53.100是怎么输出NO的,没有匹配是不是输出YES么?

write answer 切换为英文 切换为中文


转发分享