問８ 次のプログラムの説明及びプログラムを読んで，設問１，２に答えよ。

　二つの文字列の差異を測る指標に編集距離がある。編集距離の概念は，文書比較や 検索キーワードの候補の提示などに用いられている。編集距離とは，１文字の追加操作又は 削除操作を繰り返し適用し，ある文字列を別の文字列に変換するのに必要な最小の操作回数である。 例えば文字列 "abcabba" を文字列 "cbabac" に変換する場合，図１に示す操作１〜５によって変換が 完了する。図１は，最小の操作回数で変換する一例を示しており，編集距離は５となる。

図１　文字列 "abcabba" を文字列 "cbabac" に変換する場合の例

　関数 CalcEditDistance は，二つの文字列間の編集距離を返す関数である。

(1) 変換元の文字列を Str1[]，変換先の文字列を Str2[] とする。また， 配列の添字は０から始まり，文字列 Str1[] の i 番目の文字は Str1[i−1] と表記する。 したがって，Str1[] ＝ "abcabba" の場合，１番目の文字 ＝ Str1[Ø]＝ "a"， ２番目の文字 ＝ Str1[1] ＝ "b" となる。Str2[] についても同様である。

(2) 関数 CalcEditDistance は，エディットグラフと呼ばれるグラフの最短距離取得問題の 考え方に基づいて，編集距離を求めている。編集距離の求め方は次のとおりである。

図２　Strl[]＝"abcabba"，Str2[]＝"cbabac" の場合の
エディットグラフ（左）と最短移動距離となる経路の例（右）

(4) 関数 CalcEditDistance では，点（Ø，Ø）から点（X，Y）への最短移動距離を D[X，Y] に求めている。D[X，Y] は，既に算出されている D[X−1，Y−1]， D[X，Y−1]，D[X−1，Y] を用いて求めることができる。これによって編集距離を算出している。

〔関数 CalcEditDistance の引数と返却値〕

　関数 CalcEditDistance の引数の仕様は，次のとおりである。各配列の添字は，0 から始まる。

　関数 CalcEditDistance では，次の関数 Min を使用している。

〔関数 Min の仕様〕

　引数として与えられた二つ以上の整数値の中で最も小さい値を返却値とする。

〔プログラム〕

設問１　プログラム中の に入れる正しい答えを， 解答群の中から選べ。

a に関する解答群

b に関する解答群

設問２　次の記述中の に入れる正しい答えを， 解答群の中から選べ。

　Str1[]＝"peace"，Str2[]＝"people" の場合のエディットグラフは となる。
　CalcEditDistance("peace"，5，"people"，6) を実行した場合， 関数 CalcEditDistance が終了するまでに行αは 回実行され， 行βは 回実行される。また， 返却値は となる。 ここで，関数 CalcEditDistance 中の ， には正しい答えが入っているものとする。

c に関する解答群

d に関する解答群

e に関する解答群

f に関する解答群