2004年11月号のクイズ (解答)

テーマ:
クイズの解答。わざと黄色を指定して見にくくしてあるので、選択して反転するか、他のウィンドウにコピーして読んでください。

fromIndex がこの文字列の長さよりも大きい場合に、部分文字列として空(長さ0)の文字列を指定したときの結果を文字列の長さにするため。

解説。まず、Math.min(fromIndex, this.length()) の性質を考える。this.length() という条件を追加することで、fromIndex が元の文字列の長さよりも大きい場合、k の値は、fromIndex 以上ではなく、this.length() 以上で調べることになる。

例えば「phinloda」という文字列の場合、this.length() は8だから、8より大きな fromIndex を指定したときも、この処理仕様としては、8番目以降に指定した部分文字列があるかどうかを調べることになる。

しかし、「phinloda」という文字列の長さは8だ。最後の「a」ですら、最初を0として7番目の文字である。8番目以降を調べるというのはどういうことか?

public boolean startsWith(String prefix, int toffset)

の仕様は、リファレンスマニュアルには次のように書いてある。

toffset が負の値の場合、あるいは String オブジェクトの長さより大きい場合、結果は false。そうでない場合は、結果は

    this.subString(toffset).startsWith(prefix)

の式の結果と同じ


8というのは「phinloda」の長さに等しい。「より大きい」ではないのだ。だから、結果は、this.subString(toffset).startsWith(prefix) を調べることになる。

しかし、this.subString(toffset) は空の文字列である。空の文字列にマッチする部分文字列など存在するだろうか? それが一つだけあるのだ。空の文字列は、空の文字列の部分文字列なのである。つまり、"".startsWith("") は trueなのだ。

要するに「Phinloda」という文字列に対して、indexOf("", 10000) は 8 なのである。indexOf の仕様が、もし

k >= fromIndex && this.startsWith(str, k)

という条件で調べるようになっていたら、「Phinloda」という文字列に対して、indexOf("", 10000) は -1 になってしまう。

ちなみに、これがどういう意味を持つかというと、ある種のアルゴリズムを実装するのに都合がいいらしい。具体的にどういう場合に便利なのかというと、えーと、分からないです、実は。すみません。考えておきます。
AD

2004年11月号のクイズ

テーマ:
C Magazine 2004年11月号の「あっぱれご意見番」に出したクイズの話。

問題について簡単に紹介しておく。このクイズは Java を知らないと解けないのだが、まず、Java を知らない人向けに大雑把なコンセプトを紹介しておく。

ある文字列の指定位置以後に部分文字列が含まれていればその位置を返す処理を考えてください。但し、指定した部分文字列が見つからない場合は、-1を返すものとする。位置は、文字列の最初を0番目とする。ま、ありふれた処理ではあります。

具体的に考えてみよう。例えば「phinloda」という文字列の、0番目以後に「in」がふくまれているかどうか。0番目というのは日常生活では違和感のある表現だが、プログラムでは割と使われるもので、ここでは先頭を意味している。この文字列の2番目から「in」という文字列が現れるから、この場合は、2という値を返せばよい。

2番目以後が指定されたらどうか。2番目以後というのは、pが0番目、hが1番目なので、2番目の文字「i」以後だけを調べることになる。ちょうど2番目から始まる文字列が「in」だから、この場合は、2という値を返せばよい。

3番目以後が指定されたらどうか。「phinloda」という文字列の3番目以後には「in」という文字列は存在しない。この場合は、-1という値を返すことになる。

このような処理を書くのは、効率を考えなければ簡単だ。実際、Java の String クラスにはその処理が最初から用意されていて、indexOf という名前が付いている。ということで、ここからが本題になってくるのだが、とりあえず、Cマガジンのコラムの最後に書いた問題部分を紹介する。

Java 2 SE 1.4.0 のリファレンスマニュアルには、String.indexOf というメソッドが次のように説明されている。

----

public int indexOf(String str, int fromIndex)

指定されたインデックス以降で、指定された部分文字列がこの文字列内で最初に出現する位置のインデックスを返します。返される整数は、次の最小値 k になります。

k >= Math.min(fromIndex, this.length()) && this.startsWith(str, k)

このような k の値が存在しない場合、-1 が返されます。


----

なお、実際のマニュアルは、this.length() ではなく str.length() と書いてあるかもしれないが、Cマガジンに書いたように、これは誤りで this.length() が正しい。

問題は、なぜ

k >= fromIndex && this.startsWith(str, k)

ではなく、

k >= Math.min(fromIndex, this.length()) && this.startsWith(str, k)

という条件になっているのか、というものだ。なお、この問題は一般的なものではなく、Java 特有の振る舞いを知らないと解けないので、念の為。

(つづく)
AD