AOJ : 1203 - Napoleon's Grumble

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1203

アルファベットと, その他の無駄な記号が混じった文字列が1行に与えられます.
この文字列からアルファベット以外を取り除いた文字列を作って, その文字列の中にある回文を探す問題です(ただし, 出力仕様に注意).
出力は, 解候補を辞書式順に並べて出力しなければ, AOJでは通りません.

アルゴリズム

Javaで解くと無駄な文字を消す操作がラクだと思ったので, Javaで解きました.
まず, toUpperCase()によってアルファベットを全て大文字にして, replaceAll()によってアルファベット以外を消去しました.
外側のループで, 回文を探す文字列の長さ (i) を決めてやって, 内側のループで先頭からインデックス (j) をまわしていきます.
もし, インデックス j の位置から i 文字分切り取った文字列が回文であったならば, それを答えとして記憶します.
その後, この回文である文字列の内側に, 回文である文字列があれば, それは解にしてはいけない候補として記憶します.

プログラム

import java.io.*;
import java.util.*;

public class Main{
  //与えられた文字列が回文であるかを判定する
  private static boolean isPalindrome(String s){
    int n = s.length();
    for(int i=0;i<n/2;i++){
      if(s.charAt(i) != s.charAt(n-i-1)) return false;
    }
    return true;
  }

  public static void main(String[] args)throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    while(br.ready()){
      String s = br.readLine().toUpperCase().replaceAll("[^A-Z]","");
      int n = s.length();
      TreeSet<String> set = new TreeSet<String>(); //解候補
      HashSet<String> bad = new HashSet<String>(); //解にしてはいけない候補
      boolean[][] flg = new boolean[n][n]; //[i][j]がtrueであるとき : インデックスiからjへの文字列は解候補にしてはいけない

      //文字列長を決める
      for(int i=n;i>=3;i--){
        //検索の先頭添字を決める
        for(int j=0;j<=n-i;j++){
          if(flg[j][j+i-1]) continue; //解候補でないならとばす
          String sub = s.substring(j,j+i);

          if(isPalindrome(sub) && !bad.contains(sub)){
            set.add(sub);
            //内側の回文を解にしてはいけない候補に入れる
            for(int k=0;k<i/2;k++){
              flg[j+k][j+i-k-1] = true;
              bad.add(sub.substring(k,i-k));
            }
          }
        }
      }

      System.out.println(set.toString().replaceAll("\\[|\\]|,",""));
    }
  }
}