問題3-4の実装をベースに,以下の仕様を満たすプログラムに改変し,スペル訂正器を作成せよ.

  1. 標準入力から辞書ファイル(単語の集合 $V$)を読み込む.
    • 辞書ファイルの先頭行には単語の総数 $|V|$ が書かれている.
    • 辞書ファイルの2行目以降には,$|V|$ 個の単語が1行1単語形式で書かれている.
  2. 標準入力から文字列$x$を読み込み,$\min_{y \in V} {\rm ld}(x, y)$を与える単語$y$をすべて標準出力に書き出す(ただし,${\rm ld}(x,y)$は文字列$x$と$y$の編集距離を表す).編集距離が最小となる単語$y$が複数あるときは,スペースで区切って出力する(どのような順序で出力しても構わない).
  3. 2の処理を標準入力が終端(EOF)に到達するまで繰り返す.
  4. 辞書ファイルに書かれている単語,および標準入力から与えられる単語の文字数は25未満で,空白文字は含まないと仮定してよい.

/opt/local/enshu/data/gsl_vocab.txtGSL (General Service List)のデータファイルを加工して作成した英単語リストを準備した.プログラムを自動採点システムに提出する前に,以下のコマンドでスペルチェッカの動作を確認せよ.ターミナルから入力した単語の綴りの修正候補が表示されるはずである.

$ cat /opt/local/enshu/data/gsl_vocab.txt - | ./a.out

出力例

# excelent
> excellent
# programu
> program

#は標準入力,>は標準出力を表す.