C言語での文字列検索アルゴリズム実装: 素朴な照合とKMPアルゴリズム

C言語で文字列検索を行うプログラムを作成する際、素朴な方法や高度なアルゴリズムを利用することができます。本記事では、指定された2つのアルゴリズム、素朴な文字列照合プログラムとKMP（Knuth-Morris-Pratt）アルゴリズムについて解説し、実装方法を示します。

1. 素朴な文字列照合アルゴリズム
2. KMPアルゴリズムの解説と実装
3. KMPアルゴリズムの利点と用途
4. まとめ

1. 素朴な文字列照合アルゴリズム

最も基本的な文字列照合の方法は、ターゲットテキスト（t）内でパターン（p）を探すというものです。この方法では、テキストのすべての位置に対してパターンと照合を行い、完全に一致する位置を返します。

下記はその実装例です:

#include 
#include 

int text_search(char t[], char p[]) {
    int n = strlen(t);
    int m = strlen(p);
    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (t[i + j] != p[j]) break;
        }
        if (j == m) return i;  // パターンが一致した位置を返す
    }
    return -1;  // 一致しなければ-1を返す
}

void main(void) {
    char t[] = "cadabeabafababc";
    char p[] = "ababc";
    int r = text_search(t, p);
    if (r != -1) {
        printf("Found at %d\n", r);
    } else {
        printf("Not found\n");
    }
}

2. KMPアルゴリズムの解説と実装

KMPアルゴリズムは、文字列検索の効率を大幅に改善するアルゴリズムです。通常の文字列照合では、パターンと文字列が一致しないたびに最初から再チェックする必要がありますが、KMPアルゴリズムは部分一致を利用し、すでに比較した部分を再度比較しないように最適化されています。

KMPアルゴリズムのコア部分は「next配列」の生成です。この配列は、パターン内の各位置で、次に比較するべき位置を指し示します。これにより、不要な比較を省略することができます。

下記はKMPアルゴリズムの実装例です:

#include 
#include 
#include 

int text_search(char t[], char p[]) {
    int i = 0, j = 0, n, m;
    int *next;
    n = strlen(t);
    m = strlen(p);
    next = (int*) malloc(sizeof(int) * m);

    i = -1;
    next[0] = -1;
    for (j = 1; j < m; j++) {
        while (i >= 0 && p[j] != p[i]) {
            i = next[i];
        }
        i++;
        if (p[j] != p[i]) next[j] = i;
        else next[j] = next[i];
    }

    // next配列の表示
    for (i = 0; i < m; i++) {
        printf("%d, ", next[i]);
    }
    printf("\n");

    i = 0;
    for (j = 0; j < n; j++) {
        while (i >= 0 && t[j] != p[i]) {
            i = next[i];
        }
        i++;
        if (i == m) return j - m + 1;
    }
    return -1;
}

void main(void) {
    char t[] = "cadabeabafababc";
    char p[] = "ababc";
    int r = text_search(t, p);
    if (r != -1) {
        printf("Found at %d\n", r+1);
    } else {
        printf("Not found\n");
    }
}