|
今回は、ある文字列の中に特定の文字列が含まれているかを調べ、含まれているならその位置を調べる検索アルゴリズムを考えてみます。これは、データベースの検索やテキスト処理ツールなどでも、最も基本的な処理ですね。 まあ、たいていの処理系にはあらかじめ検索用の関数が用意されているので、別に今回のような方法を考える必要はないのですが。 文字列の検索文字列を検索する一番簡単な方法は、検索対象の文字列の最初から探す文字列（キー文字列）が含まれているか一字づつ探していく事です。例えば、３文字のキー文字列の最初の文字が見つかったら、検索対象文字列のその次の文字がキー文字列の２字めと一致するか調べ、一致したら３字目を調べます。もし３文字目まで一致すれば、３文字のキー文字列がすべて一致したわけで、検索対象文字列のその部分にキー文字列が含まれている事になるでしょう。
検索対象文字列 abcdefghijk
キー文字列 efg
最初から１字づつ調べる
a b c d e f g h i j k
↑
一致しないのでそのまま次のb へ。
a b c d e f g h i j k
↑
最初の文字が一致したので、その次の文字がキー文字列の２字目（f）か調べる。
a b c d e f g h i j k
↑
２字目も一致。３字目を調べる。
a b c d e f g h i j k
↑
３字目（キー文字列の最後）まで一致したので、キー文字列を検出。
一致した最初の位置（５文字目）を文字列の最初の位置として返す。
この文字列検索アルゴリズムをプログラムにすると、以下のような感じです。
private int search(String textS,String keyS) {
char text[],key[];
int i,j,textN,keyN;
textN=textS.length(); /* 検索対象文字列の長さ */
keyN=keyS.length(); /* キー文字列の長さ */
if (keyN==0)
return -1;
text=textS.toCharArray(); /* 文字列を配列に */
key=keyS.toCharArray();
for (i=0;i<textN-keyN+1;i++) { /* 検索 */
j=0; /* 比較位置を初期化 */
/* 一文字ずつ比較 */
while (j<keyN && text[i+j]==key[j]) {
j++; /* 比較位置を一つずらす */
}
/* キー文字列と一致すればその位置を返す */
if (j==keyN)
return i;
}
return -1; /* 最後まで一致しなければー１を返す */
}
この例では、変数i が現在比較されているテキスト文字列の最初の位置を、j が現在比較されているキー文字列の位置を表しています。構造としては、テキスト文字列をi の位置から調べていき、キー文字列と一致した文字があればwhileループ内でj が増やされていく２重ループですね。jがキー文字列の長さにまで増やされればキー文字列が見つかった事を意味します。 プログラムまず、text に検索対象の文字列をkey に検索するキーを入れてください。次に、search! ボタンをクリックすると検索が開始されます。キーが見つかると、その部分が選択状態となり反転表示されて下の方に見つかった位置が表示されるので、テキスト文字列とキー文字列を見比べてみましょう（ただし、環境によっては反転表示されない場合もあるかもしれません）。見つからなかった場合は、下の方に-1が表示されます。 |