JavaのindexOf関数はナイーブ法で実装されているらしい

• indexOf関数とは
  • 実際のソースを見よう
  • ナイーブ法ってなんぞや

indexOf関数とは

ドキュメントはここ。

indexOfの細かい使い方は説明はしないが、簡単にいうと二つの文字列を比較して重複する箇所がある場合にその開始部分のインデックスを返すというもの。

実際のソースを見よう

どのように実装されているのかが気になったので
jdkの中に存在するsrc.zipを解凍して確認してみることに。

 public int indexOf(String str) {
        return indexOf(str, 0);
    }

public int indexOf(String str, int fromIndex) {
        return indexOf(value, 0, value.length,
                str.value, 0, str.value.length, fromIndex);
    }


static int indexOf(char[] source, int sourceOffset, int sourceCount,
            char[] target, int targetOffset, int targetCount,
            int fromIndex) {
        if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
        }
        if (fromIndex < 0) {
            fromIndex = 0;
        }
        if (targetCount == 0) {
            return fromIndex;
        }

        char first = target[targetOffset];
        int max = sourceOffset + (sourceCount - targetCount);

        for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }

            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + targetCount - 1;
                for (int k = targetOffset + 1; j < end && source[j]
                        == target[k]; j++, k++);

                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        return -1;
    }

引数がstr一つのみのindexOfを呼ぶと関数の中で自動的に引数をstr,0で次のindexOfに、そしてまた次のindexOfに、という流れで呼び出している。

最後に呼び出されている関数に関してはナイーブ法となっている。

ナイーブ法ってなんぞや

ナイーブ法とは文字列を探索するときに愚直に全ての文字列を走査すること。

例を出してみると、

hoge = "あいうえお"
foo =  "えお"

fooの文字列がhoge中に存在するかを確かめたいとする。

ナイーブ法では最初にhogeの1文字目であるあとfooの1文字目であるえを比べる。
これをhogeのn文字目とfooの1文字目が合致するまで繰り返すというものだ。

仮に合致した場合にはfooの文字をインクリメントし、hoge完全一致すればhogeとfooの文字列が合致した最初のインデックスを返すようになっている。

最後まで合致しない場合には-1を返す。

この方法ではテキストの文字数を M、パターンの文字数を N と仮定するとO(MNになる)。(同じ文字が何度も続く場合を考慮した場合の最悪計算量であり、実質的にはO(N)になることがほとんど。)

文字列探索はKMPアルゴリズムとかBM法とかあるのでそちらで書いてみるのも有意義っぽいのでいつか書きたい。