「1409 77377」の編集履歴(バックアップ)一覧はこちら
「1409 77377」(2006/04/16 (日) 23:08:07) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
**1409 77377
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1409
**解答方針
「単語を入力するための数字列」から「単語文字列」へのMultiMapを用意し,与えられた単語をすべて登録する.JavaではC++のようなMultiMapがないので,HashMapとArrayListの組み合わせでMultiMapを実現している.
入力数字列の解析はDFSで行う.DFSはStateクラス単位で行う.Stateクラスは「今までにマッチした単語のリスト」rwords と「まだ単語とマッチしていない入力数字列」buffer を保持する.初期状態ではrwodsは空で,bufferは入力数字列そのものである.DFSである状態をスタックから取り出したら,bufferを1文字ずつ50文字まで読み込んでいく.読み込んだ数字列がある単語の入力数字列と一致したら,その単語をrwordsに追加しbufferから読み込んだ入力数字列を削って,スタックに入れる.bufferを50文字まで読んだらその状態を破棄する.状態をスタックから取り出したときbufferが0文字ならマッチ成功なので,rwordsをSentenceクラスのインスタンスに変換して,出力文集合sentencesetに登録する.なお,Sentenceクラスは,文を辞書式順序で並べるために,Comparable<Sentence>を実装している.
**解答例
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true){
int n = sc.nextInt();
if(n==0) break;
// make dictionary
HashMap<String,ArrayList<String>> dictionary =
new HashMap<String,ArrayList<String>>();
for(int i=0;i<n;i++){
String word = sc.next();
String seq = toButtonSequence(word);
if(dictionary.containsKey(seq)){
dictionary.get(seq).add(word);
}
else{
dictionary.put(seq,new ArrayList<String>());
dictionary.get(seq).add(word);
}
}
// analyze input sequence
String input = sc.next();
Stack<State> st = new Stack<State>();
TreeSet<Sentence> sentenceset = new TreeSet<Sentence>();
st.push(new State(input));
while(!st.empty()){
State state = st.pop();
if(state.isEnd()){
String[] sentence = new String[state.rwords.size()];
sentence = state.rwords.toArray(sentence);
sentenceset.add(new Sentence(sentence));
}
for(int i=1;i<=50&&i<=state.buffer.length();i++){
String rbuf = state.buffer.substring(0,i);
if(dictionary.containsKey(rbuf)){
ArrayList<String> hitwordlist = dictionary.get(rbuf);
for(String w:hitwordlist){
State newstate = new State(state);
newstate.buffer = newstate.buffer.substring(i);
newstate.rwords.add(w);
st.push(newstate);
}
}
}
}
//output
for(Sentence set:sentenceset){
String[] words = set.words;
int wordnum = words.length;
for(int i=0;i<wordnum;i++){
if(i==wordnum-1) System.out.print(words[i]);
else System.out.print(words[i]+" ");
}
System.out.println(".");
}
System.out.println("--");
}
}
public static char toButton(char c){
if (c<='c') return '2';
else if(c<='f') return '3';
else if(c<='i') return '4';
else if(c<='l') return '5';
else if(c<='o') return '6';
else if(c<='s') return '7';
else if(c<='v') return '8';
else return '9';
}
public static String toButtonSequence(String s){
char[] seq = new char[s.length()];
for(int i=0;i<s.length();i++){
seq[i] = toButton(s.charAt(i));
}
return new String(seq);
}
}
class State{
ArrayList<String> rwords;
String buffer;
State(String buf){
rwords = new ArrayList<String>();
buffer = buf;
}
State(State s){
rwords = new ArrayList<String>(s.rwords);
buffer = new String(s.buffer);
}
public boolean isEnd(){
if(buffer.length()==0) return true;
else return false;
}
}
class Sentence implements Comparable<Sentence>{
String[] words;
Sentence(String[] words) {
this.words = words;
}
public int compareTo(Sentence s){
int l1 = this.words.length;
int l2 = s.words.length;
for(int i=0;i<l1&&i<l2;i++){
if(this.words[i].compareTo(s.words[i])!=0)
return this.words[i].compareTo(s.words[i]);
}
return l1-l2;
}
}