hihoCoder- 403 Forbidden（Trie樹問題 C解決）

題目1 : 403 Forbidden

時間限制:10000ms

單點時限:1000ms

記憶體限制:256MB

描述

Little Hi runs a web server. Sometimes he has to deny access from a certain set of malicious IP addresses while his friends are still allow to access his server. To do this he writes N rules in the configuration file which look like:

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

Each rule is in the form: allow | deny address or allow | deny address/mask.

When there comes a request, the rules are checked in sequence until the first match is found. If no rule is matched the request will be allowed. Rule and request are matched if the request address is the same as the rule address or they share the same first mask digits when both written as 32bit binary number.

For example IP “1.2.3.4” matches rule “allow 1.2.3.4” because the addresses are the same. And IP “128.127.8.125” matches rule “deny 128.127.4.100/20” because 10000000011111110000010001100100 (128.127.4.100 as binary number) shares the first 20 (mask) digits with 10000000011111110000100001111101 (128.127.8.125 as binary number).

Now comes M access requests. Given their IP addresses, your task is to find out which ones are allowed and which ones are denied.

輸入

Line 1: two integers N and M.

Line 2-N+1: one rule on each line.

Line N+2-N+M+1: one IP address on each line.

All addresses are IPv4 addresses(0.0.0.0 - 255.255.255.255). 0 <= mask <= 32.

For 40% of the data: 1 <= N, M <= 1000.

For 100% of the data: 1 <= N, M <= 100000.

輸出

For each request output “YES” or “NO” according to whether it is allowed.

樣例輸入

5 5
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
1.2.3.4
1.2.3.5
1.1.1.1
100.100.100.100
219.142.53.100
           

樣例輸出

YES
YES
NO
YES
NO
           

每個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))的。

#include<iostream>
#include<sstream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<cctype>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int INF = ;
char ch1[INF][];
char ch2[INF];
const int INTMAX = ;
struct TrieNode {
    int num;  //記錄規則序号
    TrieNode *next[];
    bool exist;
};

TrieNode * create() {
  TrieNode* node = (TrieNode *)malloc(sizeof(TrieNode));
  node -> num = INTMAX;
  node -> exist = false;
  memset(node -> next, , sizeof(node -> next));
  return node;
}

void Trie_insert(TrieNode * root, char *word, int num) {
    TrieNode * node = root;

    char *p = word;
    int id;
    while(*p) {
        id = *p - '0';
        if(node -> next[id] == NULL) {
            node -> next[id] = create();
        }
        node = node -> next[id];
        ++p;
        if(node -> exist) {
            return ;
        }
    }
    node -> exist = true;
    node -> num = num;
}

int TrieSearch(TrieNode *root, char *word) {
    TrieNode* node = root;
    char *p = word;
    int id;
    int seq = INTMAX;
    while(*p) {
        if(node -> exist) {
            seq = min(node -> num, seq);
        }
        id = (*p) - '0';
        node = node -> next[id];
        if(node == NULL) {
            return seq;
        }
        p++;
    }
    if(node -> exist) {
        seq = min(node -> num, seq);
    }
    return seq;
}

void dfs(char *rtn, int n, int len) {
    if(n /  > ) {
        dfs(rtn, n / , len + );
        rtn[ - len] = n %  + ;
    } else {
        for(int i = ; i <  - len; i++) {
            rtn[i] = '0';
        }
        rtn[ - len] = n + ;
    }
    rtn[] = '\0';
    return ;
}
char* convert(char *ip) {
    char *rtn = new char[], *newHead = ip;
    int total = ;
    char *p = strchr(ip, '.');
    rtn[] = '\0';
    while(p != NULL) {
        int digit = ;

        for(; ip < p; ip++) {
            digit = digit *  + (*ip) - ;
        }
        char num[];
        dfs(num, digit, );
        num[] = '\0';
        strcat(rtn, num);
        ip += ;
        if(strchr(p + , '.') != NULL) {
            p = strchr(p + , '.');
        } else if(strchr(p + , '/') != NULL) {
            p = strchr(p + , '/');
        } else if(strchr(p + , '\0') != NULL){
            if((*p) == '\0' || (*p) == '/') {
                break;
            }
            p = strchr(p + , '\0');
        } else {
            break;
        }
    }
    int digit = ;
    if(strchr(newHead, '/') != NULL) {
        char* p = strchr(ip, '\0');
        for(; ip < p; ip++) {
            digit = digit *  + (*ip) - ;
        }
        rtn[digit] = '\0';
    } else {
        rtn[] = '\0';
    }
    return rtn;
}

int main() {

    int n, m;
    while(~scanf("%d%d", &n, &m)) {
        TrieNode* root = create();
        for(int i = ; i < n; i++) {
            scanf("%s %s", ch1[i], ch2);
            Trie_insert(root, convert(ch2), i);

        }
        for(int i = ; i < m; i++) {
            char req[];
            scanf("%s", req);
            int seq = TrieSearch(root, convert(req));
            if(seq == INTMAX) {
                printf("YES\n");
            } else {
                printf("%s\n", strcmp(ch1[seq], "allow") ==  ? "YES" : "NO");
            }
        }
    }

    return ;
}
/*
3 35
deny 123.0.0.0/3
allow 127.0.0.1
allow 123.234.12.23/3
123.0.0.0

*/