先頭へ戻る

文字列の後ろの方から文字列を探す | Programming Place Plus C言語編 逆引き

Programming Place Plus トップページ -- C言語編 -- 逆引き

先頭へ戻る

この章の概要

この章の概要です。

目的

文字列の中から、任意の文字列を探したいとします。ただし、文字列の末尾に近いものを探すという条件があるとしましょう。

先頭に近いものを探す方法は、「逆引き 文字列から文字列を探す」で取り上げています。

逆向きに探すという意味ではないことに注意してください。たとえば、"abcdabcd" から "abc" を探す場合、"abc" は2つありますが、後ろから4文字目のところから始まる "abc" のほうを見つけてほしいということです。

この要求はつまり、ある文字列が含まれているかどうかだけではなく、どこにあるかも重要だということでもあります。したがって、bool型の結果を返すのではなく、見つかった文字列を指すポインタを返すように考えます。添字が必要なら、ポインタの減算(第32章)で対応できます。

/*
    文字列の後ろの方から文字列を探す。

    引数
        s: 対象の文字列
        target: 探す文字列
    戻り値
        見つかったら、その文字列の先頭の文字のメモリアドレス。
        見つからなかったらヌルポインタ。
*/
char* find_last_string(const char* s, const char* target);


int main(void)
{
    const char s[] = "abcdabcd";

    // 最後に現れる位置を調べる
    char* p = find_last_string(s, "abc");

    // 何文字目にあったか
    if (p != NULL) {
        ptrdiff_t index = p - s;
    }

    return 0;
}

方法①(自力で実装する)

標準ライブラリには、この目的に合った関数がありません。先頭から文字を探す strchr関数に対して、末尾に近い文字を探す strrchr関数があるように、先頭から文字列を探す strstr関数に対応する strrstr関数があってもよさそうですが、標準にはありません。

自力で実装します。

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

/*
    文字列の後ろの方から文字列を探す。

    引数
        s: 対象の文字列
        target: 探す文字列
    戻り値
        見つかったら、その文字列の先頭の文字のメモリアドレス。
        見つからなかったらヌルポインタ。
*/
char* find_last_string(const char* s, const char* target)
{
    const size_t s_len = strlen(s);
    const size_t target_len = strlen(target);

    // target の方が長いのなら、見つかることはない
    if (s_len < target_len) {
        return NULL;
    }

    // target の文字数を考慮して、探す意味がある一番後ろ側の位置を計算
    size_t index = s_len - target_len;

    for (;;) {

        // 現在位置で一致確認
        if (strncmp(&s[index], target, target_len) == 0) {
            return (char*)&s[index];
        }

        // 一致しなかったら、探す位置を先頭側へ1文字ずらす
        // すでに先頭を見ていたのなら終了
        if (index <= 0) {
            return NULL;
        }
        --index;
    }

    return NULL;
}


int main(void)
{
    const char s[] = "abcdabcd";

    char* p = find_last_string(s, "abc");
    if (p == NULL) {
        puts("not found");
    }
    else {
        printf("found. (%td)\n", p - s);
    }

    return 0;
}

実行結果:

found. (4)

まず、対象の文字列 (s) と探したい文字列 (target) の長さを取得し、探す意味のある最も後ろ側の位置を計算します。s が 8文字、target が 3文字なら、&s[5] から調べ始めます。&s[6] から調べても、残りの文字数が 2文字しかないので、3文字の target と一致するはずがないからです。また、s より target の方が長い場合は、さっさと「見つからない」と返してしまえます。

文字列の一致確認は、strncmp関数で行っています。一致すれば、今回の調査位置のメモリアドレスを返して終了します。一致しなければ、探す位置を s の先頭の側へ1文字ずらして続行します。

探す位置が s の先頭(index == 0) のときに strncmp関数が「一致しない」と判定した場合、target は含まれていませんから、ヌルポインタを返して終了させます。

この実装が必ずしも効率的であるということではありません。アルゴリズムとデータ構造編があつかうような内容になってしまうので、ここでは触れませんが、文字列探索には、ボイヤームーア法(参考リンク1)など、より効率的なアルゴリズムがあります。


参考リンク

  1. ボイヤー-ムーア文字列検索アルゴリズム | Wikipedia

更新履歴



逆引きのトップページへ

C言語編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー