AOJ1111 Cyber Guardian

問題リンク Cyber Guardian

• 概要

N個のパケットフィルタとM個のパケットが与えられる。M個のパケットの中で送信が許されるものを答えよ。
パケットは送信元アドレスと送信先アドレスと本文からなる。アドレスは'0'〜'9'と'?'の文字からなる8文字の文字列で表される。'?'はワイルドカードで任意の1文字とマッチングする。
パケットフィルタは許可を許す記述(permit)と許さない記述(deny)の2種類がある。パケットの送信元と送信先のアドレスが両方ともフィルタのアドレスにマッチしたらそのフィルタが適用される。
N個のフィルタのうち、複数のフィルタにマッチした場合、フィルタの優先順位が高い方のものが適用される。入力で後で入力されるものほど優先順位が高いものとする。また、どのフィルタにも引っかからなかったパケットは送信されない。
N, M <= 1024

• 解法

8文字の文字列マッチングさえ作ってしまえば勝ちです。
入力されたフィルタのうち、後ろの方からマッチングにかけ、マッチした且つpermitならそのパケットは送信されます。それ以外は全て送信されません。

• ソース

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//Cyber Guardian
public class AOJ1111 {

	boolean match(String s, String t){
		for(int i=0;i<16;i++){
			if(s.charAt(i)=='?'||t.charAt(i)=='?')continue;
			if(s.charAt(i)!=t.charAt(i))return false;
		}
		return true;
	}

	class P{
		String s, t, m;
		public P(String s, String t, String m) {
			this.s = s;
			this.t = t;
			this.m = m;
		}
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			int m = sc.nextInt();
			if((n|m)==0)break;
			String[] rule = new String[n];
			String[] d = new String[n];
			for(int i=0;i<n;i++){
				rule[i] = sc.next();
				d[i] = sc.next()+sc.next();
			}
			List<P> l = new ArrayList<P>();
			while(m--!=0){
				P p = new P(sc.next(), sc.next(), sc.next());
				String z = p.s+p.t;
				for(int i=n-1;i>=0;i--){
					if(match(z, d[i])){
						if(rule[i].equals("permit"))l.add(p);
						break;
					}
				}
			}
			System.out.println(l.size());
			for(P p:l)System.out.println(p.s+" "+p.t+" "+p.m);
		}
	}

	public static void main(String[] args) {
		new AOJ1111().run();
	}
}