PKU : 3098 - Frugal Search
問題概要
http://poj.org/problem?id=3098
辞書の中に, 指定されたパターンの文字列があるかどうか答える問題.
パターンに一致する文字列は, 複数あるかもしれないが, 辞書式順で先になる文字列を出力すること.
アルゴリズム
実装するだけ.
辞書式順で先になる文字列を出力してると思ってたはずが, 本当はしてなかったことに気付かず手間取った.
プログラム
static int n; static boolean[][] dicFlg; static int search(int[] flg){ for(int i=0;i<n;i++){ boolean f = true; boolean f2 = false; for(int j=(int)'a';j<=(int)'z';j++){ if(flg[j] == 1 && !dicFlg[i][j] || flg[j] == -1 && dicFlg[i][j]){ f = false; break; } if(flg[j] == 2 && dicFlg[i][j]){ f2 = true; } } if(f && f2) return i; } return -1; } public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); while(true){ ArrayList<String> dic = new ArrayList<String>(); while(true){ String s = br.readLine(); if(s.equals("#")) return; if(s.equals("*")) break; dic.add(s); } Collections.sort(dic); n = dic.size(); dicFlg = new boolean[n][128]; for(int i=0;i<n;i++){ for(char ch : dic.get(i).toCharArray()){ dicFlg[i][ch] = true; } } while(true){ String ts = br.readLine(); if(ts.equals("**")) break; String[] ss = ts.split("\\|"); int idx = -1; String ans = null; for(String s : ss){ int[] flg = new int[128]; for(int i=0;i<s.length();i++){ if(s.charAt(i) == '-'){ flg[s.charAt(i+1)] = -1; i++; } else if(s.charAt(i) == '+'){ flg[s.charAt(i+1)] = 1; i++; } else{ flg[s.charAt(i)] = 2; } } idx = search(flg); if(idx != -1 && (ans == null || ans.compareTo(dic.get(idx)) > 0)){ ans = dic.get(idx); } } System.out.println(ans == null ? "NONE" : ans); } System.out.println("$"); } }