トップC-Tips > 簡単な文字列探索法

簡単な文字列探索法

何万、何十万語という大量の単語の中から、ある単語を選ぶには、 ハッシュ法、二分木、バイナリサーチなどそれなりの技法が必要となるが、 数十、数百語からの探索は、通常はごく簡単な方法で十分である。 ここでは、自分がしばしば使っている方法を紹介する。

1.strstr関数による文字列探索(完全一致)

下のプログラムのWordsのように、 検索被対象の単語群をスペースを空けてつなぎ合わせ、全体を一つの文字列としておく。 ここで、文字列の先頭および末尾にもスペースを挿入しておくことに注意されたい。

例えば、"big" がこの単語群に含まれるか調べるときには、 strstr(" big ", Words) を実行する。 戻り値が NULL でなければ含まれており、NULL ならば含まれていない。

search1.c
#include <stdio.h>
#include <string.h>

char *Words = " big smaller search strong apple weak apples little pineapple may ";

// 完全一致
void contain(char *word, char *words) {
    char buf[256], *p;

    sprintf(buf, " %s ", word);
    p = strstr(words, buf);
    printf("単語<%s>は含まれて%s\n", word, p != NULL ? "います" : "いません"); 
}

int main() {
    contain("big", Words);
    contain("small", Words);
}

このプログラムの実行結果を下に示す。"smaller" という単語はあるが、完全一致ではない。

c:\MH\www\c-tips\string>search1
単語<big>は含まれています
単語<small>は含まれていません

2.前方一致検索

単語の語尾の方は違っていてもよい、というのが前方一致検索である。 プログラム例(search1.cと同じ部分は省略した)と実行結果を下に示す。

search2.c
// 前方一致
void contain(char *word, char *words) {
    char buf[256], *p, *q, *r;

    printf("\"%s\"を前方一致検索します\n", word);
    sprintf(buf, " %s", word);
    for (p = words; (q = strstr(p, buf)) != NULL; p = r) {
        r = strchr(q+1, ' ');	// 後ろのスペースの位置
        printf("単語\"%.*s\"が見つかりました\n", r-q-1, q+1); 
    }
}

int main() {
    contain("apple", Words);
}
c:\MH\www\c-tips\string>search2
"apple"を前方一致検索します
単語"apple"が見つかりました
単語"apples"が見つかりました

3.後方一致検索

前方一致とは逆に、語尾が一致しておればよい、というのが後方一致検索である。 プログラム例(search2.cと同じ部分は省略した)と実行結果を下に示す。

search3.c
// 後方一致
void contain(char *word, char *words) {
    char buf[256], *p, *q, *r;

    printf("\"%s\"を後方一致検索します\n", word);
    sprintf(buf, "%s ", word);
    for (p = words; (q = strstr(p, buf)) != NULL; p = r) {
        r = strchr(q, ' ');	// 後ろのスペースの位置
        while (q[-1] != ' ') q--;	// 単語の先頭を探す
        printf("単語\"%.*s\"が見つかりました\n", r-q, q); 
    }
}
c:\MH\www\c-tips\string>search3
"apple"を後方一致検索します
単語"apple"が見つかりました
単語"pineapple"が見つかりました

4.部分一致検索

検索語が含まれておればよい、というのが部分一致検索である。 プログラム例(search3.cと同じ部分は省略した)と実行結果を下に示す。

search4.c
// 部分一致
void contain(char *word, char *words) {
    char buf[256], *p, *q, *r;

    printf("\"%s\"を部分一致検索します\n", word);
    sprintf(buf, "%s", word);
    for (p = words; (q = strstr(p, buf)) != NULL; p = r) {
        r = strchr(q, ' ');	// 後ろのスペースの位置
        while (q[-1] != ' ') q--;	// 単語の先頭を探す
        printf("単語\"%.*s\"が見つかりました\n", r-q, q); 
    }
}
c:\MH\www\c-tips\string>search4
"apple"を部分一致検索します
単語"apple"が見つかりました
単語"apples"が見つかりました
単語"pineapple"が見つかりました

5.区切り文字について

ここに示したプログラムでは単語間の区切り文字をスペースとした。 単語に含まれない文字であれば何でもよい。 '\r' や '\t' のようなエスケープ文字にしてもよい。