hiho149周 - 数据结构 trie树
2024-08-24 22:04:42
坑点:accept和deny的ip可能相同,需加个判断
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#define OO 0x0fffffff
#define MIN(a,b) (a<b?a:b)
using namespace std; struct NODE{
NODE *left,*right;
int aid;
bool accept;
NODE(){
aid = -;
left = right = NULL;
}
};
NODE root;
int digits[];
void add_acl(int id,char *acl,bool accept){
NODE *ptr = &root;
for(int i=;acl[i];i++){
if(acl[i]=='') {
if(ptr->right==NULL) ptr->right = new NODE();
ptr = ptr->right;
}
else{
if(ptr->left==NULL) ptr->left = new NODE();
ptr = ptr->left;
}
}
if(ptr->aid<){
ptr->aid = id;
ptr->accept = accept;
}
}
void parse_ip(char *input,char *output,int len){
sscanf(input,"%d.%d.%d.%d",digits+,digits+,digits+,digits+);
int i,j;
for(i=;i<;i++){
int td = digits[i];
for(j=(i+)*-;j>=i*;j--){
output[j] = ''+(td&);
td>>=;
}
}
output[len]='\0';
}
int main(){
int m,n,len;
char type[],str[],ip[];
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
cin>>type>>str;
len = ;
std::size_t idx = string(str).find('/');
if(idx!=std::string::npos){
str[idx]='\0';
len = atoi(str+idx+);
}
parse_ip(str,ip,len);
add_acl(i,ip,type[]=='a');
}
for(int i=;i<m;i++){
cin>>str;
parse_ip(str,ip,);
NODE *ptr = &root;
int ans = OO;
bool accept = true;
int iptr = ;
while(ptr){
if(ptr->aid>=) {
if(ptr->aid<ans){
ans = ptr->aid;
accept = ptr->accept;
}
}
if(ip[iptr]=='') ptr=ptr->right;
else ptr=ptr->left;
iptr++;
}
puts(accept?"YES":"NO");
}
return ;
}
最新文章
- 细读cow.osg
- Mac配置Qt环境——Could not resolve SDK path for &#39;macosx10.8&#39;
- windows系统下ftp上传下载和一些常用命令
- Docker SSH+NGHINX+MYSQL
- dede的幻灯片除了首页其他页面也显示的方法,
- Struts2 Convention插件的使用(4)使用@Action注解返回json数据
- BootStrap glyphicons字体图标
- Java为何大行其道
- python cookielib
- 【Unity 3D】教程(1)建立场景
- 论JSON的重要性☞异步上传过程中data取多组值的方法
- git 分支的创建与提交
- nginx截获客户端请求
- Android简易实战教程--第四十一话《vitamio网络收音机》
- Latex ";Error: File ended while scanning use of \@xdblarge";
- 用SharedPreference或文件的方式存储数据
- mybatis获取insert插入之后的id
- Python&#183;——进程1
- 7F - 无限的路
- Spring MVC的核心控制器DispatcherServlet的作用