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("\\[|\\]|,","")); } } }