【C言語】strstr関数を使わずに文字列を検索する方法を解説

2023-09-172024-06-03

この記事では、C言語で文字列を検索する方法を紹介します。

目次から探す

strstr関数を使わずに文字列を検索する方法

文字列を検索する際には、C言語の標準ライブラリであるstrstr関数を使用することが一般的です。

しかし、strstr関数を使わずに文字列を検索する方法も存在します。

ループを使った方法

ループを使った方法では、文字列を一文字ずつ比較しながら検索を行います。

具体的な手順は以下の通りです。

検索対象の文字列と検索する文字列の長さを取得します。
検索対象の文字列を一文字ずつ順番に比較します。
検索する文字列の先頭文字と検索対象の文字列の現在の位置の文字を比較します。
一致しない場合は、検索対象の文字列の次の位置に移動します。
一致する場合は、検索する文字列の次の文字と検索対象の文字列の次の位置の文字を比較します。
全ての文字が一致する場合は、検索が成功したと判断します。

以下に、ループを使った方法のサンプルコードを示します。

#include <stdio.h>
int search(char* haystack, char* needle) {
    int haystack_len = strlen(haystack);
    int needle_len = strlen(needle);
    for (int i = 0; i <= haystack_len - needle_len; i++) {
        int j;
        for (j = 0; j < needle_len; j++) {
            if (haystack[i + j] != needle[j]) {
                break;
            }
        }
        if (j == needle_len) {
            return i;
        }
    }
    return -1;
}
int main() {
    char haystack[] = "This is a sample string";
    char needle[] = "sample";
    int result = search(haystack, needle);
    if (result == -1) {
        printf("検索対象の文字列が見つかりませんでした。\n");
    } else {
        printf("検索対象の文字列が見つかりました。位置: %d\n", result);
    }
    return 0;
}

上記のコードでは、search関数を定義しています。

この関数は、検索対象の文字列と検索する文字列を引数として受け取り、検索結果の位置を返します。

main関数では、search関数を呼び出して検索を行い、結果を表示しています。

ループを使った方法はシンプルで理解しやすいですが、文字列の長さに比例して処理時間が増えるため、大きな文字列を検索する場合には効率が悪いと言えます。

KMP法を使った方法

KMP法は、より効率的に文字列を検索するためのアルゴリズムです。

KMP法では、検索する文字列の中で一致しなかった文字に基づいて、検索位置をスキップすることができます。

具体的な手順は以下の通りです。

検索対象の文字列と検索する文字列の長さを取得します。
検索する文字列に対して、一致しなかった場合の次の検索位置を事前に計算します。
検索対象の文字列を一文字ずつ順番に比較しながら検索を行います。
一致しない場合は、検索位置をスキップします。
一致する場合は、検索する文字列の次の文字と検索対象の文字列の次の位置の文字を比較します。
全ての文字が一致する場合は、検索が成功したと判断します。

以下に、KMP法を使った方法のサンプルコードを示します。

#include <stdio.h>
void computeLPSArray(char* needle, int needle_len, int* lps) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < needle_len) {
        if (needle[i] == needle[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}
int search(char* haystack, char* needle) {
    int haystack_len = strlen(haystack);
    int needle_len = strlen(needle);
    int lps[needle_len];
    computeLPSArray(needle, needle_len, lps);
    int i = 0;
    int j = 0;
    while (i < haystack_len) {
        if (needle[j] == haystack[i]) {
            j++;
            i++;
        }
        if (j == needle_len) {
            return i - j;
        } else if (i < haystack_len && needle[j] != haystack[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;
}
int main() {
    char haystack[] = "This is a sample string";
    char needle[] = "sample";
    int result = search(haystack, needle);
    if (result == -1) {
        printf("検索対象の文字列が見つかりませんでした。\n");
    } else {
        printf("検索対象の文字列が見つかりました。位置: %d\n", result);
    }
    return 0;
}

上記のコードでは、computeLPSArray関数とsearch関数を定義しています。

computeLPSArray関数は、検索する文字列に対して、一致しなかった場合の次の検索位置を計算するための配列を作成します。

search関数では、検索対象の文字列と検索する文字列を引数として受け取り、検索結果の位置を返します。

main関数では、search関数を呼び出して検索を行い、結果を表示しています。

KMP法はループを使った方法よりも効率的に文字列を検索することができますが、実装がやや複雑であるため、理解には時間がかかるかもしれません。

以上が、strstr関数を使わずに文字列を検索する方法についての解説です。

ループを使った方法とKMP法を使った方法を紹介しましたが、どちらの方法を選ぶかは検索する文字列の長さや処理速度の要件によって異なる場合があります。

適切な方法を選んで、効率的な文字列検索を行いましょう。