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("$");
  }
}