prithivMLmods/Coder-Stat

1 2<h1>3Cyber Guardian4</h1>5 6 7<p>In the good old days, the Internet was free from fears and8terrorism. People did not have to worry about any cyber criminals or mad9computer scientists. Today, however, you are facing atrocious crackers 10wherever you are, unless being disconnected. You have to protect11yourselves against their attacks.</p>12 13<p>Counting upon your excellent talent for software construction and14strong sense of justice, you are invited to work as a cyber15guardian. Your ultimate mission is to create a perfect firewall system16that can completely shut out any intruders invading networks and protect17children from harmful information exposed on the Net. However, it is18extremely difficult and none have ever achieved it before. As the first 19step, instead, you are now requested to write a software simulator20under much simpler assumptions.</p>21 22<p>In general, a firewall system works at the entrance of a local network23of an organization (e.g., a company or a university) and enforces its local24administrative policy. It receives both inbound and outbound packets25(note: data transmitted on the Net are divided into small segments26called packets) and carefully inspects them one by one whether or not27each of them is legal. The definition of the legality may28vary from site to site or depend upon the local administrative29policy of an organization. Your simulator should accept data representing30not only received packets but also the local administrative policy.</p>31 32<p>For simplicity in this problem we assume that each network packet33consists of three fields: its source address, destination address, and34message body. The source address specifies the computer or appliance35that transmits the packet and the destination address specifies the36computer or appliance to which the packet is transmitted. An address37in your simulator is represented as eight digits such as 03214567 or3831415926, instead of using the standard notation of IP addresses39such as 192.168.1.1. Administrative policy is described in40filtering rules, each of which specifies some collection of41source-destination address pairs and defines those packets with the42specified address pairs either legal or illegal. </p>43 44<h2>Input</h2>45 46<p>The input consists of several data sets, each of which represents47filtering rules and received packets in the following format:</p>48 49<dir>50<i>n</i> <i>m</i><br>51<i>rule</i><sub>1</sub><br>52<i>rule</i><sub>2</sub><br>53<dir>...</dir><br>54<i>rule<sub>n</sub></i><br>55<i>packet</i><sub>1</sub><br>56<i>packet</i><sub>2</sub><br>57<dir>...</dir><br>58<i>packet</i><sub>m</sub><br>59</dir>60 61<p>The first line consists of two non-negative integers <i>n</i> and62<i>m</i>. If both <i>n</i> and <i>m</i> are zeros, this means the end63of input. Otherwise, <i>n</i> lines, each representing a filtering64rule, and <i>m</i> lines, each representing an arriving packet, follow65in this order. You may assume that <i>n</i> and <i>m</i> are less than66or equal to 1,024.</p>67 68<p>Each <i>rule<sub>i</sub></i> is in one of the following formats:</p>69 70<dir>71<p>permit <i>source-pattern</i> <i>destination-pattern</i></p>72<p>deny <i>source-pattern</i> <i>destination-pattern</i></p>73</dir>74 75<p>A <i>source-pattern</i> or <i>destination-pattern</i> is a76character string of length eight, where each character is either a77digit ('0' to '9') or a wildcard character '?'. For instance,78"1????5??" matches any address whose first and fifth digits are '1'79and '5', respectively. In general, a wildcard character matches any80single digit while a digit matches only itself.</p>81 82<p>With the keywords "permit" and "deny", filtering rules specify83legal and illegal packets, respectively. That is, 84if the source and destination addresses of a packed are matched with85<i>source-pattern</i> and <i>destination-pattern</i>, respectively, it 86is <i>permitted</i> to pass the firewall or the request is87<i>denied</i> according to the keyword. Note that a permit rule 88and a deny rule can contradict since they may share the same source89and destination address pair. For the purpose of conflict resolution,90we define a priority rule: <i>rule<sub>i</sub></i> has a higher priority over91<i>rule<sub>j</sub></i> if and only if <i>i</i> &gt; <i>j</i>. For92completeness, we define the default rule: any packet is illegal unless93being explicitly specified legal by some given rule.</p>94 95<p>A packet is in the following format:</p>96 97<dir>98<p><i>source-address</i> <i>destination-address</i> <i>message-body</i></p>99</dir>100 101<p>Each of the first two is a character string of length eight that102consists solely of digits. The last one is a character string103consisting solely of alphanumeric characters ('a' to 'z', 'A' to 'Z',104and '0' to '9'). Neither whitespaces nor special characters can occur105in a message body. You may assume that it is not empty and that its106length is at most 50. </p>107 108 109<p>You may also assume that there is exactly one110space character between any two adjacent fields in an input line111representing a rule or a packet.</p>112 113<h2>Output</h2>114 115<p>For each data set, print the number of legal packets in the first116line, followed by all legal packets in the same order as they occur in117the data set. Each packet must be written exactly in one line. If the118data set includes two packets consisting of the same source and119destination addresses and the same message body, you should consider120them different packets and so they must be written in different121lines. Any extra whitespaces or extra empty lines must not be122written. </p>123 124<h2>Sample Input</h2>125<pre>2 5126permit 192168?? ?12??34?127deny 19216899 012343?512819216711 11233340 HiIamACracker12919216891 01234345 Hello13019216899 01234345 HiIamAlsoACracker13119216809 11200340 World13200000000 99999999 TheEndOfTheWorld1331 2134permit 12345678 2345678913519216891 01234345 Hello13612345678 23456789 Hello1370 0138</pre>139 140<h2>Output for the Sample Input</h2>141<pre>142214319216891 01234345 Hello14419216809 11200340 World145114612345678 23456789 Hello147</pre>148 149