| 第１種情報処理技術者試験 |
1995年度 ＝ 平成7年度 |
午前 |
問6 |
文字列P = p1 p2 … pmの中に文字列T = t1 t2 … tnが部分列として含まれているか否かを判定する。Pの部分列p1 p2 … pn, p2 p3 … pn+1, … に対して順にTと一致するかどうかを調べると、文字の照合回数は、どのオーダになるか。ここで、n≪mとする。
| ア m
| イ m n
| ウ m n2
| エ m log n
| オ n log m
|
イ
力まかせ法による文字列照合に関する問題です。
Pの部分列p1 p2 … pnと、文字列T = t1 t2 … tnが一致するかどうかを照合し、一致しなければ、Pの部分列p2 p3 … pn+1と文字列Tが一致するかどうかを照合するといった手順を繰り返します。
したがって、文字の照合回数は、文字列Pの比較回数×文字列Tの文字数となります。前者はn－mで、後者はmです。ただし、題意よりn≪mですから、前者はnとみなせます。
したがって、正解は選択肢イのmnとなります。
