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

  1. 標準入力から辞書ファイル(単語の集合 $V$)を読み込む.
    • 辞書ファイルの先頭行には単語の総数 $|V|$ が書かれている.
    • 辞書ファイルの2行目以降には,$|V|$ 個の単語が1行1単語形式で書かれている.
  2. 標準入力から単語(文字列)$x$を読み込む.
  3. 入力された単語$x$と辞書内の単語$y$ $(\in V)$の編集距離を求める.
  4. $x$との編集距離が最小となる単語$y$を1位としたときに,1位から3位までの編集距離と単語を以下に示す出力フォーマットに従って標準出力に表示せよ.各順位の結果を表示した後に改行せよ.ただし,編集距離が同じ場合は,辞書の前方にある単語を上位とする.
  5. 標準入力が終端 (EOF) に到達するまで2~4の処理を繰り返す.
  6. 辞書ファイルに書かれている単語,および標準入力から与えられる単語の文字数は25未満で,空白文字は含まないと仮定してよい.

出力フォーマット

rank:⊔順位,⊔ed⊔=⊔編集距離,⊔string⊔=⊔単語

は,半角スペースを示す.

実行例

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

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

出力例

# programu
> rank: 1, ed = 1, string = program
> rank: 2, ed = 3, string = progress
> rank: 3, ed = 5, string = broad

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

malloc() を使う場合の注意点

辞書ファイルが大きいため,適切に malloc()free() を使わないと自動採点システムにおいてタイムアウトになります. タイムアウトでエラーになった場合は,malloc()free() を確認してください.