第3章：文字列理論とアルゴリズムの世界

• 平均ケース: O(n)

3.2.3 Knuth-Morris-Pratt（KMP）アルゴリズム

1977年、ドナルド・クヌース（Donald Knuth）、ジェームズ・モリス（James Morris）、ヴォーン・プラット（Vaughan Pratt）が独立に発見し、共同で発表した画期的なアルゴリズムです。

核心的なアイデア

ミスマッチが発生したとき、すでに比較した情報を活用して、無駄な比較をスキップします。

例: text = "ABABABCA", pattern = "ABABC"

ナイーブ法:
Position 0: ABABABCA
            ABABC    ← 4文字マッチ後、ミスマッチ
            ↓ 1文字進める
Position 1: ABABABCA
             ABABC   ← 最初からやり直し

![KMP Failure Function](/Users/hackhike/.gemini/antigravity/brain/bc43455d-719e-4889-8da1-eb68d30dc6a7/kmp_failure_function_1764871179579.png)

失敗関数（Failure Function）の計算

失敗関数 π[j] は、pattern[0..j] の最長の「真の接頭辞かつ接尾辞」の長さを表します。

// 失敗関数の計算：O(m)
void compute_failure_function(const char *pattern, int *failure)
{
    int m = strlen(pattern);
    failure[0] = 0;

    int k = 0;  // 最長の接頭辞=接尾辞の長さ

    for (int i = 1; i < m; i++)
    {
        // ミスマッチの場合、より短い接頭辞=接尾辞を探す
        while (k > 0 && pattern[k] != pattern[i])
            k = failure[k - 1];

        // マッチした場合
        if (pattern[k] == pattern[i])
            k++;

        failure[i] = k;
    }
}

// 失敗関数の例
// pattern = "ABABC"
// failure = [0, 0, 1, 2, 0]
//
// i=0: "A"       → 真の接頭辞=接尾辞なし → 0
// i=1: "AB"      → 真の接頭辞=接尾辞なし → 0
// i=2: "ABA"     → "A"が接頭辞かつ接尾辞 → 1
// i=3: "ABAB"    → "AB"が接頭辞かつ接尾辞 → 2
// i=4: "ABABC"   → 真の接頭辞=接尾辞なし → 0

KMPアルゴリズムの完全実装

typedef struct {
    int *positions;
    int count;
    int capacity;
} MatchResult;

MatchResult *kmp_search(const char *text, const char *pattern)
{
    int n = strlen(text);
    int m = strlen(pattern);

    // 結果を格納する構造体
    MatchResult *result = malloc(sizeof(MatchResult));
    result->positions = malloc(sizeof(int) * (n / m + 1));
    result->count = 0;
    result->capacity = n / m + 1;

    if (m == 0)
        return result;

    // 失敗関数の計算
    int *failure = malloc(sizeof(int) * m);
    compute_failure_function(pattern, failure);

    int j = 0;  // パターン内の現在位置

    for (int i = 0; i < n; i++)
    {
        // ミスマッチの場合、失敗関数を使用
        while (j > 0 && pattern[j] != text[i])
            j = failure[j - 1];

        // マッチした場合
        if (pattern[j] == text[i])
            j++;

        // パターン全体がマッチ
        if (j == m)
        {
            result->positions[result->count++] = i - m + 1;
            j = failure[j - 1];  // 次のマッチを探す
        }
    }

    free(failure);
    return result;
}

計算量

• 前処理（失敗関数）: O(m)
• 検索: O(n)
• 合計: O(n + m)

3.2.4 Boyer-Moore アルゴリズム

1977年、ロバート・ボイヤー（Robert Boyer）とJ・ストロザー・ムーア（J Strother Moore）が発表した、実用上最も高速な文字列検索アルゴリズムの一つです。

革新的なアイデア

• 後ろから比較: パターンを右から左に比較する
• Bad Character Rule: ミスマッチ文字を利用してスキップ
• Good Suffix Rule: マッチした部分を利用してスキップ

例: text = "TRUSTHARDWORKNOT", pattern = "HARDWORK"

![Boyer-Moore Shift](/Users/hackhike/.gemini/antigravity/brain/bc43455d-719e-4889-8da1-eb68d30dc6a7/boyer_moore_shift_1764871202764.png)

Bad Character Rule の実装

void compute_bad_char(const char *pattern, int bad_char[256])
{
    int m = strlen(pattern);

    // すべての文字をパターン長に初期化
    for (int i = 0; i < 256; i++)
        bad_char[i] = m;

    // パターン中の各文字の最右出現位置を記録
    for (int i = 0; i < m - 1; i++)
        bad_char[(unsigned char)pattern[i]] = m - 1 - i;
}

Good Suffix Rule の実装

void compute_good_suffix(const char *pattern, int *good_suffix)
{
    int m = strlen(pattern);
    int *suffix = malloc(sizeof(int) * m);

    // suffix[i] = pattern[i..m-1]とpatternの最長共通接尾辞の長さ
    suffix[m - 1] = m;
    int g = m - 1;
    int f = 0;

    for (int i = m - 2; i >= 0; i--)
    {
        if (i > g && suffix[i + m - 1 - f] < i - g)
        {
            suffix[i] = suffix[i + m - 1 - f];
        }
        else
        {
            if (i < g)
                g = i;
            f = i;
            while (g >= 0 && pattern[g] == pattern[g + m - 1 - f])
                g--;
            suffix[i] = f - g;
        }
    }

    // good_suffix テーブルの構築
    for (int i = 0; i < m; i++)
        good_suffix[i] = m;

    int j = 0;
    for (int i = m - 1; i >= 0; i--)
    {
        if (suffix[i] == i + 1)
        {
            while (j < m - 1 - i)
            {
                if (good_suffix[j] == m)
                    good_suffix[j] = m - 1 - i;
                j++;
            }
        }
    }

    for (int i = 0; i < m - 1; i++)
        good_suffix[m - 1 - suffix[i]] = m - 1 - i;

    free(suffix);
}

Boyer-Moore 完全実装

int boyer_moore_search(const char *text, const char *pattern)
{
    int n = strlen(text);
    int m = strlen(pattern);

    if (m == 0)
        return 0;
    if (m > n)
        return -1;

    // 前処理
    int bad_char[256];
    int *good_suffix = malloc(sizeof(int) * m);

    compute_bad_char(pattern, bad_char);
    compute_good_suffix(pattern, good_suffix);

    int i = 0;  // テキスト内の位置

    while (i <= n - m)
    {
        int j = m - 1;  // パターン内の位置（右端から）

        // 後ろから比較
        while (j >= 0 && pattern[j] == text[i + j])
            j--;

        if (j < 0)
        {
            // マッチ発見
            free(good_suffix);
            return i;
        }

        // シフト量を計算
        int bc_shift = bad_char[(unsigned char)text[i + j]] - (m - 1 - j);
        int gs_shift = good_suffix[j];

        // より大きいシフトを採用
        i += (bc_shift > gs_shift) ? bc_shift : gs_shift;
    }

    free(good_suffix);
    return -1;
}

計算量

• 前処理: O(m + |Σ|)
• 最悪ケース: O(nm)
• 平均・最良ケース: O(n/m) - サブリニア！

3.2.5 Rabin-Karp アルゴリズム

1987年、マイケル・ラビン（Michael Rabin）とリチャード・カープ（Richard Karp）が発表した、ハッシュ関数を利用したアルゴリズムです。

アイデア

パターンのハッシュ値を計算し、テキストの各位置のハッシュ値と比較します。ローリングハッシュ（Rolling Hash）により、効率的に次の位置のハッシュを計算できます。

ローリングハッシュ

base = 256 (または文字集合のサイズ)
prime = 大きな素数 (例: 101, 1000000007)

hash("abc") = (a × base² + b × base¹ + c × base⁰) mod prime

hash("bcd") = hash("abc")から計算：
            = (hash("abc") - a × base²) × base + d

実装

#define BASE 256
#define PRIME 1000000007

long long compute_hash(const char *str, int len)
{
    long long hash = 0;
    for (int i = 0; i < len; i++)
    {
        hash = (hash * BASE + (unsigned char)str[i]) % PRIME;
    }
    return hash;
}

// べき乗の計算（モジュラ演算）
long long power(long long base, int exp, long long mod)
{
    long long result = 1;
    base %= mod;
    while (exp > 0)
    {
        if (exp & 1)
            result = (result * base) % mod;
        exp >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

int rabin_karp_search(const char *text, const char *pattern)
{
    int n = strlen(text);
    int m = strlen(pattern);

    if (m > n)
        return -1;

    // パターンのハッシュ
    long long pattern_hash = compute_hash(pattern, m);

    // 最初のウィンドウのハッシュ
    long long text_hash = compute_hash(text, m);

    // base^(m-1) mod PRIME を事前計算
    long long h = power(BASE, m - 1, PRIME);

    for (int i = 0; i <= n - m; i++)
    {
        // ハッシュが一致したら実際に比較
        if (text_hash == pattern_hash)
        {
            int j;
            for (j = 0; j < m; j++)
            {
                if (text[i + j] != pattern[j])
                    break;
            }
            if (j == m)
                return i;  // 真のマッチ
        }

        // ローリングハッシュ
        if (i < n - m)
        {
            text_hash = (BASE * (text_hash - (unsigned char)text[i] * h)
                        + (unsigned char)text[i + m]) % PRIME;

            // 負の値を正に補正
            if (text_hash < 0)
                text_hash += PRIME;
        }
    }

    return -1;
}

複数パターン検索

Rabin-Karpの真価は、複数のパターンを同時に検索する場合に発揮されます。

typedef struct {
    const char *pattern;
    long long hash;
} PatternInfo;

int multi_pattern_search(const char *text, const char **patterns, int num_patterns)
{
    int n = strlen(text);

    // パターンの最短・最長を求める
    int min_len = INT_MAX, max_len = 0;
    for (int i = 0; i < num_patterns; i++)
    {
        int len = strlen(patterns[i]);
        if (len < min_len) min_len = len;
        if (len > max_len) max_len = len;
    }

    // 各パターンのハッシュを計算
    PatternInfo *infos = malloc(sizeof(PatternInfo) * num_patterns);
    for (int i = 0; i < num_patterns; i++)
    {
        infos[i].pattern = patterns[i];
        infos[i].hash = compute_hash(patterns[i], strlen(patterns[i]));
    }

    // 検索（各長さごとに処理）
    for (int len = min_len; len <= max_len; len++)
    {
        long long text_hash = compute_hash(text, len);
        long long h = power(BASE, len - 1, PRIME);

        for (int i = 0; i <= n - len; i++)
        {
            // 同じ長さのパターンと比較
            for (int p = 0; p < num_patterns; p++)
            {
                if ((int)strlen(patterns[p]) == len &&
                    text_hash == infos[p].hash &&
                    strncmp(text + i, patterns[p], len) == 0)
                {
                    printf("Pattern '%s' found at position %d\n",
                           patterns[p], i);
                }
            }

            // ローリングハッシュ
            if (i < n - len)
            {
                text_hash = (BASE * (text_hash - (unsigned char)text[i] * h)
                            + (unsigned char)text[i + len]) % PRIME;
                if (text_hash < 0)
                    text_hash += PRIME;
            }
        }
    }

    free(infos);
    return 0;
}

3.2.6 Aho-Corasick アルゴリズム

1975年、アルフレッド・エイホ（Alfred Aho）とマーガレット・コラシック（Margaret Corasick）が発表した、複数パターン同時検索アルゴリズムです。

構造

• トライ（Trie）: パターンの共通接頭辞を共有する木構造
• 失敗リンク: KMPの失敗関数を多パターンに一般化
• 出力リンク: マッチしたパターンを報告

#define ALPHABET_SIZE 256

typedef struct AhoCorasickNode {
    struct AhoCorasickNode *children[ALPHABET_SIZE];
    struct AhoCorasickNode *failure;
    struct AhoCorasickNode *output;
    int pattern_index;  // -1 if not a terminal
} ACNode;

typedef struct {
    ACNode *root;
    const char **patterns;
    int num_patterns;
} AhoCorasick;

ACNode *create_node()
{
    ACNode *node = calloc(1, sizeof(ACNode));
    node->pattern_index = -1;
    return node;
}

void build_trie(AhoCorasick *ac)
{
    for (int i = 0; i < ac->num_patterns; i++)
    {
        ACNode *current = ac->root;
        const char *pattern = ac->patterns[i];

        for (int j = 0; pattern[j]; j++)
        {
            unsigned char c = pattern[j];

            if (!current->children[c])
                current->children[c] = create_node();

            current = current->children[c];
        }

        current->pattern_index = i;
    }
}

void build_failure_links(AhoCorasick *ac)
{
    // BFSのためのキュー
    ACNode **queue = malloc(sizeof(ACNode*) * 10000);
    int front = 0, rear = 0;

    // 深さ1のノードの失敗リンクはルート
    for (int c = 0; c < ALPHABET_SIZE; c++)
    {
        if (ac->root->children[c])
        {
            ac->root->children[c]->failure = ac->root;
            queue[rear++] = ac->root->children[c];
        }
    }

    // BFSで残りのノードを処理
    while (front < rear)
    {
        ACNode *current = queue[front++];

        for (int c = 0; c < ALPHABET_SIZE; c++)
        {
            ACNode *child = current->children[c];
            if (!child)
                continue;

            queue[rear++] = child;

            // 失敗リンクを計算
            ACNode *f = current->failure;
            while (f && !f->children[c])
                f = f->failure;

            child->failure = f ? f->children[c] : ac->root;

            // 出力リンク
            if (child->failure->pattern_index >= 0)
                child->output = child->failure;
            else
                child->output = child->failure->output;
        }
    }

    free(queue);
}

void aho_corasick_search(AhoCorasick *ac, const char *text,
                         void (*callback)(int pos, int pattern_idx))
{
    ACNode *current = ac->root;

    for (int i = 0; text[i]; i++)
    {
        unsigned char c = text[i];

        // 失敗リンクをたどる
        while (current != ac->root && !current->children[c])
            current = current->failure;

        if (current->children[c])
            current = current->children[c];

        // マッチを報告
        if (current->pattern_index >= 0)
        {
            int len = strlen(ac->patterns[current->pattern_index]);
            callback(i - len + 1, current->pattern_index);
        }

        // 出力リンクをたどる
        ACNode *temp = current->output;
        while (temp)
        {
            int len = strlen(ac->patterns[temp->pattern_index]);
            callback(i - len + 1, temp->pattern_index);
            temp = temp->output;
        }
    }
}

計算量

• 前処理: O(Σ|patterns|)
• 検索: O(n + k) (kはマッチ数)

3.2.7 Suffix Array と LCP Array

接尾辞配列は、テキストの全ての接尾辞を辞書順にソートした配列です。1990年代に開発され、バイオインフォマティクスで広く使用されています。

定義

text = "banana$"

すべての接尾辞:
0: banana$
1: anana$
2: nana$
3: ana$
4: na$
5: a$
6: $

辞書順にソート:
6: $
5: a$
3: ana$
1: anana$
0: banana$
4: na$
2: nana$

Suffix Array: SA = [6, 5, 3, 1, 0, 4, 2]

LCP配列（Longest Common Prefix）

隣接する接尾辞の最長共通接頭辞の長さです。

LCP[i] = SA[i]とSA[i-1]の最長共通接頭辞の長さ

SA[0]: $        LCP[0] = 0 (定義により)
SA[1]: a$       LCP[1] = 0 ($とa$の共通接頭辞なし)
SA[2]: ana$     LCP[2] = 1 (a$とana$は"a"を共有)
SA[3]: anana$   LCP[3] = 3 (ana$とanana$は"ana"を共有)
SA[4]: banana$  LCP[4] = 0
SA[5]: na$      LCP[5] = 0
SA[6]: nana$    LCP[6] = 2 (na$とnana$は"na"を共有)

実装（SA-IS法の簡易版）

typedef struct {
    int *sa;      // Suffix Array
    int *lcp;     // LCP Array
    int n;        // テキスト長
} SuffixArray;

// 比較関数
int suffix_compare(const void *a, const void *b, void *text)
{
    const char *t = (const char *)text;
    int i = *(const int *)a;
    int j = *(const int *)b;
    return strcmp(t + i, t + j);
}

// 簡易的なSuffix Array構築（O(n² log n)）
SuffixArray *build_suffix_array(const char *text)
{
    int n = strlen(text);

    SuffixArray *sa = malloc(sizeof(SuffixArray));
    sa->n = n;
    sa->sa = malloc(sizeof(int) * n);
    sa->lcp = malloc(sizeof(int) * n);

    // 初期化
    for (int i = 0; i < n; i++)
        sa->sa[i] = i;

    // ソート（qsort_rを使用）
    qsort_r(sa->sa, n, sizeof(int), suffix_compare, (void *)text);

    // LCP計算（Kasai's algorithm）
    int *rank = malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
        rank[sa->sa[i]] = i;

    int k = 0;
    for (int i = 0; i < n; i++)
    {
        if (rank[i] == 0)
        {
            sa->lcp[0] = 0;
            k = 0;
            continue;
        }

        int j = sa->sa[rank[i] - 1];

        while (i + k < n && j + k < n && text[i + k] == text[j + k])
            k++;

        sa->lcp[rank[i]] = k;

        if (k > 0)
            k--;
    }

    free(rank);
    return sa;
}

// パターン検索（二分探索）
int suffix_array_search(SuffixArray *sa, const char *text, const char *pattern)
{
    int left = 0, right = sa->n - 1;
    int m = strlen(pattern);

    while (left <= right)
    {
        int mid = (left + right) / 2;
        int cmp = strncmp(text + sa->sa[mid], pattern, m);

        if (cmp == 0)
            return sa->sa[mid];
        else if (cmp < 0)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;
}

3.3 C言語における文字列の本質

3.3.1 文字列リテラルとメモリ配置

C言語の文字列は、他の高級言語とは根本的に異なります。文字列型は存在せず、「ヌル文字で終端される文字の配列」として実装されます。

文字列リテラルのメモリ配置

#include <stdio.h>

int main()
{
    // 異なる宣言方法とその違い

    // 1. 配列として宣言（スタック上、書き込み可能）
    char arr[] = "Hello";

    // 2. ポインタとして宣言（読み取り専用領域を指す）
    const char *ptr = "Hello";

    // 3. 配列のサイズを明示（余分な領域がある）
    char arr2[10] = "Hello";

    // メモリレイアウトを表示
    printf("arr address: %p (stack)\n", (void *)arr);
    printf("ptr address: %p (rodata section)\n", (void *)ptr);

    // arr は変更可能
    arr[0] = 'h';  // OK

    // ptr は変更不可（未定義動作）
    // ptr[0] = 'h';  // 危険！セグメンテーションフォルト

    return 0;
}

プロセスのメモリレイアウト

高アドレス
┌─────────────────────┐
│     Stack          │ ← ローカル変数、関数の引数
│         ↓          │
├─────────────────────┤
│                     │
│    （未使用領域）    │
│                     │
├─────────────────────┤
│         ↑          │
│     Heap           │ ← 動的に割り当てられたメモリ
├─────────────────────┤
│     BSS            │ ← 未初期化グローバル/静的変数
├─────────────────────┤
│     Data           │ ← 初期化済みグローバル/静的変数
├─────────────────────┤
│     Text/Code      │ ← プログラムコード
├─────────────────────┤
│     Read-only data │ ← 文字列リテラルなど
└─────────────────────┘
低アドレス

3.3.2 ヌル終端の歴史と設計判断

なぜC言語はヌル終端を採用したのでしょうか？

1970年代のコンテキスト

• メモリの希少性: 文字列長を別途保存するのは贅沢だった
• PDP-11 アーキテクチャ: ヌルチェックが効率的
• UNIXとの親和性: ファイル名など、可変長文字列が必要

ヌル終端 vs 長さプレフィックス

// Pascal方式（長さプレフィックス）
struct PascalString {
    unsigned char length;  // 最大255文字の制限
    char data[255];
};

// C方式（ヌル終端）
// 任意の長さをサポート、ただし長さ取得にO(n)

// 現代の実装（両方を使う）
struct ModernString {
    size_t length;
    size_t capacity;
    char *data;  // ヌル終端も保持
};

ヌル終端の利点と欠点

利点：

• メモリ効率（追加のメタデータ不要）
• 任意の長さの文字列
• シンプルなAPI

欠点：

• 長さ取得がO(n)
• バッファオーバーフローのリスク
• バイナリデータに0x00を含められない

3.3.3 文字列操作の危険性

バッファオーバーフローの歴史

1988年のMorris Wormは、fingerdプログラムのgets()関数を悪用しました。これは最初の大規模なインターネットワームでした。

// 危険なコード（絶対に使用禁止）
void vulnerable_function()
{
    char buffer[64];
    gets(buffer);  // 入力サイズのチェックなし！
}

// 攻撃者は64文字以上を入力し、
// スタック上のリターンアドレスを書き換える

2003年のSQL Slammer

SQL Serverのスタックバッファオーバーフローを悪用し、わずか10分で75,000台以上のサーバーに感染しました。

現代の防御機構

• スタックカナリア: バッファとリターンアドレスの間に検知用の値を配置
• ASLR: アドレス空間のランダム化
• NX/DEP: スタック上のコード実行禁止
• SSP: スタック破壊検出

// GCCのスタック保護を有効化
// gcc -fstack-protector-all program.c

void protected_function()
{
    char buffer[64];
    // コンパイラが自動的にカナリアを挿入
    // 関数終了時にカナリアの整合性をチェック
}

3.4 Libft文字列関数の実装

3.4.1 ft_strlen - 文字列長の測定

これまで学んだ理論を基に、実際の実装に入りましょう。

基本実装

size_t ft_strlen(const char *s)
{
    size_t len = 0;

    while (s[len] != '\0')
        len++;

    return len;
}

なぜsize_tを使うのか

// size_tは符号なし整数型
// sizeof演算子の結果型と同じ
// システムのアドレス空間で表現可能な最大サイズを保証

// 32ビットシステム: size_t = 4バイト (最大約4GB)
// 64ビットシステム: size_t = 8バイト (最大約16EB)

// 負の長さは意味がないため、符号なし型が適切

ポインタ演算版

size_t ft_strlen(const char *s)
{
    const char *start = s;

    while (*s)
        s++;

    return (s - start);
}

最適化版（ワード単位処理）

現代のCPUは一度に複数バイトを処理できます。この特性を活用した最適化です。

// glibc風の最適化実装
size_t ft_strlen_optimized(const char *s)
{
    const char *start = s;

    // アライメント調整（ワード境界まで1バイトずつ処理）
    while ((uintptr_t)s & (sizeof(size_t) - 1))
    {
        if (*s == '\0')
            return s - start;
        s++;
    }

    // ワード単位で処理
    const size_t *word_ptr = (const size_t *)s;

    // マジックナンバー（8バイト版）
    // 0x01を各バイトに配置
    const size_t lo_magic = 0x0101010101010101ULL;
    // 0x80を各バイトに配置
    const size_t hi_magic = 0x8080808080808080ULL;

    while (1)
    {
        size_t word = *word_ptr;

        // ヌル文字検出のトリック：
        // バイトが0x00の場合、word - lo_magic で最上位ビットが1になり、
        // ~word & hi_magic と AND を取ると非ゼロになる
        if (((word - lo_magic) & ~word & hi_magic) != 0)
        {
            // どのバイトがヌルか特定
            const char *cp = (const char *)word_ptr;
            for (int i = 0; i < (int)sizeof(size_t); i++)
            {
                if (cp[i] == '\0')
                    return cp - start + i;
            }
        }
        word_ptr++;
    }
}

3.4.2 ft_strcpy / ft_strlcpy - 文字列コピー

ft_strcpy（危険な関数）

char *ft_strcpy(char *dst, const char *src)
{
    char *ret = dst;

    while ((*dst++ = *src++))
        ;

    return ret;
}

ft_strlcpy（安全な代替）

OpenBSDで開発された、より安全な文字列コピー関数です。

size_t ft_strlcpy(char *dst, const char *src, size_t dstsize)
{
    size_t srclen = 0;

    // ソースの長さを計算しながらコピー
    if (dstsize > 0)
    {
        while (srclen < dstsize - 1 && src[srclen])
        {
            dst[srclen] = src[srclen];
            srclen++;
        }
        dst[srclen] = '\0';

        // 残りのソース長を計算
        while (src[srclen])
            srclen++;
    }
    else
    {
        // dstsize == 0 の場合、コピーなし
        while (src[srclen])
            srclen++;
    }

    return srclen;
}

使用例と安全性

void demonstrate_safe_copy()
{
    char buffer[10];
    const char *long_string = "This is a very long string";

    // 危険な方法
    // strcpy(buffer, long_string);  // バッファオーバーフロー！

    // 安全な方法
    size_t result = ft_strlcpy(buffer, long_string, sizeof(buffer));

    // 切り詰めが発生したかチェック
    if (result >= sizeof(buffer))
    {
        printf("Warning: string was truncated\n");
        printf("Original length: %zu, buffer size: %zu\n",
               result, sizeof(buffer));
    }

    printf("Buffer: '%s'\n", buffer);  // "This is a"
}

3.4.3 ft_strcat / ft_strlcat - 文字列連結

ft_strcat（危険な関数）

char *ft_strcat(char *s1, const char *s2)
{
    char *ret = s1;

    // s1の終端を探す
    while (*s1)
        s1++;

    // s2をコピー
    while ((*s1++ = *s2++))
        ;

    return ret;
}

ft_strlcat（安全な代替）

size_t ft_strlcat(char *dst, const char *src, size_t dstsize)
{
    size_t dst_len = 0;
    size_t src_len = 0;

    // dst の長さを計算
    while (dst_len < dstsize && dst[dst_len])
        dst_len++;

    // src の長さを計算
    while (src[src_len])
        src_len++;

    // dstsize が dst の長さ以下なら、連結不可
    if (dst_len >= dstsize)
        return dstsize + src_len;

    // 連結
    size_t i = 0;
    while (src[i] && dst_len + i < dstsize - 1)
    {
        dst[dst_len + i] = src[i];
        i++;
    }
    dst[dst_len + i] = '\0';

    return dst_len + src_len;
}

3.4.4 ft_strcmp / ft_strncmp - 文字列比較

ft_strcmp

int ft_strcmp(const char *s1, const char *s2)
{
    while (*s1 && *s1 == *s2)
    {
        s1++;
        s2++;
    }

    return (unsigned char)*s1 - (unsigned char)*s2;
}

なぜunsigned charにキャストするのか

void demonstrate_signed_char_issue()
{
    // 多くのシステムでcharはsigned
    // 0x80 (128) 以上の値は負の数として解釈される

    char a = 0x80;  // -128 (signed) または 128 (unsigned)
    char b = 0x01;  // 1

    // 間違った比較
    int wrong = a - b;  // -128 - 1 = -129 → aがbより小さいと判定

    // 正しい比較
    int correct = (unsigned char)a - (unsigned char)b;  // 128 - 1 = 127

    printf("Signed comparison: %d\n", wrong);
    printf("Unsigned comparison: %d\n", correct);
}

ft_strncmp

int ft_strncmp(const char *s1, const char *s2, size_t n)
{
    if (n == 0)
        return 0;

    while (n > 1 && *s1 && *s1 == *s2)
    {
        s1++;
        s2++;
        n--;
    }

    return (unsigned char)*s1 - (unsigned char)*s2;
}

3.4.5 ft_strchr / ft_strrchr - 文字検索

ft_strchr

char *ft_strchr(const char *s, int c)
{
    unsigned char ch = (unsigned char)c;

    while (*s)
    {
        if (*(unsigned char *)s == ch)
            return (char *)s;
        s++;
    }

    // c が '\0' の場合、終端のヌル文字を返す
    if (ch == '\0')
        return (char *)s;

    return NULL;
}

ft_strrchr

char *ft_strrchr(const char *s, int c)
{
    unsigned char ch = (unsigned char)c;
    char *last = NULL;

    while (*s)
    {
        if (*(unsigned char *)s == ch)
            last = (char *)s;
        s++;
    }

    if (ch == '\0')
        return (char *)s;

    return last;
}

3.4.6 ft_strnstr - 部分文字列検索

char *ft_strnstr(const char *haystack, const char *needle, size_t len)
{
    size_t needle_len;

    // 空のneedleは常にマッチ
    if (*needle == '\0')
        return (char *)haystack;

    needle_len = ft_strlen(needle);

    while (*haystack && len >= needle_len)
    {
        if (*haystack == *needle &&
            ft_strncmp(haystack, needle, needle_len) == 0)
        {
            return (char *)haystack;
        }
        haystack++;
        len--;
    }

    return NULL;
}

3.4.7 ft_strdup - 文字列複製

char *ft_strdup(const char *s1)
{
    size_t len = ft_strlen(s1);
    char *dup = malloc(len + 1);

    if (!dup)
        return NULL;

    // ft_memcpy または ft_strlcpy を使用
    for (size_t i = 0; i <= len; i++)
        dup[i] = s1[i];

    return dup;
}

3.5 追加の文字列関数

3.5.1 ft_substr - 部分文字列抽出

char *ft_substr(char const *s, unsigned int start, size_t len)
{
    char *substr;
    size_t s_len;

    if (!s)
        return NULL;

    s_len = ft_strlen(s);

    // startが文字列長を超える場合、空文字列を返す
    if (start >= s_len)
        return ft_strdup("");

    // 実際にコピーする長さを調整
    if (len > s_len - start)
        len = s_len - start;

    substr = malloc(len + 1);
    if (!substr)
        return NULL;

    for (size_t i = 0; i < len; i++)
        substr[i] = s[start + i];

    substr[len] = '\0';
    return substr;
}

3.5.2 ft_strjoin - 文字列結合

char *ft_strjoin(char const *s1, char const *s2)
{
    char *result;
    size_t len1;
    size_t len2;
    size_t i;

    if (!s1 || !s2)
        return NULL;

    len1 = ft_strlen(s1);
    len2 = ft_strlen(s2);

    result = malloc(len1 + len2 + 1);
    if (!result)
        return NULL;

    for (i = 0; i < len1; i++)
        result[i] = s1[i];

    for (i = 0; i < len2; i++)
        result[len1 + i] = s2[i];

    result[len1 + len2] = '\0';
    return result;
}

3.5.3 ft_strtrim - 文字列トリム

static int is_in_set(char c, char const *set)
{
    while (*set)
    {
        if (*set == c)
            return 1;
        set++;
    }
    return 0;
}

char *ft_strtrim(char const *s1, char const *set)
{
    size_t start;
    size_t end;

    if (!s1)
        return NULL;
    if (!set)
        return ft_strdup(s1);

    start = 0;
    while (s1[start] && is_in_set(s1[start], set))
        start++;

    if (!s1[start])
        return ft_strdup("");

    end = ft_strlen(s1);
    while (end > start && is_in_set(s1[end - 1], set))
        end--;

    return ft_substr(s1, start, end - start);
}

3.5.4 ft_split - 文字列分割

static size_t count_words(char const *s, char c)
{
    size_t count = 0;
    int in_word = 0;

    while (*s)
    {
        if (*s != c && !in_word)
        {
            in_word = 1;
            count++;
        }
        else if (*s == c)
        {
            in_word = 0;
        }
        s++;
    }
    return count;
}

static char *get_word(char const *s, char c, size_t *start)
{
    size_t end;
    char *word;

    // 区切り文字をスキップ
    while (s[*start] && s[*start] == c)
        (*start)++;

    // 単語の終端を探す
    end = *start;
    while (s[end] && s[end] != c)
        end++;

    // 単語をコピー
    word = ft_substr(s, *start, end - *start);
    *start = end;

    return word;
}

char **ft_split(char const *s, char c)
{
    char **result;
    size_t word_count;
    size_t i;
    size_t pos;

    if (!s)
        return NULL;

    word_count = count_words(s, c);
    result = malloc(sizeof(char *) * (word_count + 1));
    if (!result)
        return NULL;

    pos = 0;
    for (i = 0; i < word_count; i++)
    {
        result[i] = get_word(s, c, &pos);
        if (!result[i])
        {
            // エラー処理：これまでの割り当てを解放
            while (i > 0)
                free(result[--i]);
            free(result);
            return NULL;
        }
    }
    result[word_count] = NULL;

    return result;
}

3.5.5 ft_itoa - 整数から文字列への変換

static int get_num_len(int n)
{
    int len = 0;

    if (n <= 0)
        len = 1;  // 負号または0

    while (n != 0)
    {
        n /= 10;
        len++;
    }
    return len;
}

char *ft_itoa(int n)
{
    char *str;
    int len;
    long num;

    num = n;
    len = get_num_len(n);

    str = malloc(len + 1);
    if (!str)
        return NULL;

    str[len] = '\0';

    if (num == 0)
    {
        str[0] = '0';
        return str;
    }

    if (num < 0)
    {
        str[0] = '-';
        num = -num;
    }

    while (num > 0)
    {
        str[--len] = (num % 10) + '0';
        num /= 10;
    }

    return str;
}

3.5.6 ft_strmapi - 文字列変換

char *ft_strmapi(char const *s, char (*f)(unsigned int, char))
{
    char *result;
    size_t len;
    unsigned int i;

    if (!s || !f)
        return NULL;

    len = ft_strlen(s);
    result = malloc(len + 1);
    if (!result)
        return NULL;

    for (i = 0; i < len; i++)
        result[i] = f(i, s[i]);

    result[len] = '\0';
    return result;
}

3.5.7 ft_striteri - 文字列反復処理

void ft_striteri(char *s, void (*f)(unsigned int, char*))
{
    unsigned int i;

    if (!s || !f)
        return;

    for (i = 0; s[i]; i++)
        f(i, &s[i]);
}

3.6 実践的なアプリケーション

3.6.1 簡易的なシェルのコマンドパーサー

typedef struct s_command {
    char *name;
    char **args;
    int argc;
    char *input_file;
    char *output_file;
    int append_mode;
} t_command;

t_command *parse_command(const char *line)
{
    t_command *cmd = calloc(1, sizeof(t_command));
    char **tokens;
    int i;

    if (!cmd)
        return NULL;

    // 空白で分割
    tokens = ft_split(line, ' ');
    if (!tokens || !tokens[0])
    {
        free(cmd);
        return NULL;
    }

    cmd->name = ft_strdup(tokens[0]);

    // 引数とリダイレクトを解析
    i = 1;
    cmd->args = malloc(sizeof(char *) * 100);
    cmd->argc = 0;

    while (tokens[i])
    {
        if (ft_strcmp(tokens[i], "<") == 0 && tokens[i + 1])
        {
            cmd->input_file = ft_strdup(tokens[++i]);
        }
        else if (ft_strcmp(tokens[i], ">") == 0 && tokens[i + 1])
        {
            cmd->output_file = ft_strdup(tokens[++i]);
            cmd->append_mode = 0;
        }
        else if (ft_strcmp(tokens[i], ">>") == 0 && tokens[i + 1])
        {
            cmd->output_file = ft_strdup(tokens[++i]);
            cmd->append_mode = 1;
        }
        else
        {
            cmd->args[cmd->argc++] = ft_strdup(tokens[i]);
        }
        i++;
    }
    cmd->args[cmd->argc] = NULL;

    // tokensを解放
    for (i = 0; tokens[i]; i++)
        free(tokens[i]);
    free(tokens);

    return cmd;
}

3.6.2 URLパーサー

typedef struct s_url {
    char *scheme;    // http, https, ftp
    char *host;
    char *port;
    char *path;
    char *query;
    char *fragment;
} t_url;

t_url *parse_url(const char *url_str)
{
    t_url *url = calloc(1, sizeof(t_url));
    char *pos;
    char *temp;

    if (!url)
        return NULL;

    temp = ft_strdup(url_str);
    pos = temp;

    // スキーム（://の前）
    char *scheme_end = ft_strnstr(pos, "://", ft_strlen(pos));
    if (scheme_end)
    {
        *scheme_end = '\0';
        url->scheme = ft_strdup(pos);
        pos = scheme_end + 3;
    }
    else
    {
        url->scheme = ft_strdup("http");
    }

    // フラグメント（#以降）
    char *fragment = ft_strchr(pos, '#');
    if (fragment)
    {
        url->fragment = ft_strdup(fragment + 1);
        *fragment = '\0';
    }

    // クエリ（?以降）
    char *query = ft_strchr(pos, '?');
    if (query)
    {
        url->query = ft_strdup(query + 1);
        *query = '\0';
    }

    // パス（/以降）
    char *path = ft_strchr(pos, '/');
    if (path)
    {
        url->path = ft_strdup(path);
        *path = '\0';
    }
    else
    {
        url->path = ft_strdup("/");
    }

    // ポート（:以降）
    char *port = ft_strchr(pos, ':');
    if (port)
    {
        url->port = ft_strdup(port + 1);
        *port = '\0';
    }

    // ホスト（残り）
    url->host = ft_strdup(pos);

    free(temp);
    return url;
}

3.6.3 設定ファイルパーサー

typedef struct s_config_entry {
    char *key;
    char *value;
    struct s_config_entry *next;
} t_config_entry;

typedef struct s_config {
    t_config_entry *entries;
} t_config;

t_config *parse_config_file(const char *content)
{
    t_config *config = calloc(1, sizeof(t_config));
    char **lines;
    int i;

    if (!config)
        return NULL;

    lines = ft_split(content, '\n');
    if (!lines)
    {
        free(config);
        return NULL;
    }

    for (i = 0; lines[i]; i++)
    {
        char *line = ft_strtrim(lines[i], " \t");

        // コメントと空行をスキップ
        if (!line || line[0] == '#' || line[0] == '\0')
        {
            free(line);
            continue;
        }

        // key=value を解析
        char *equals = ft_strchr(line, '=');
        if (equals)
        {
            *equals = '\0';

            t_config_entry *entry = malloc(sizeof(t_config_entry));
            entry->key = ft_strtrim(line, " \t");
            entry->value = ft_strtrim(equals + 1, " \t\"'");
            entry->next = config->entries;
            config->entries = entry;
        }

        free(line);
        free(lines[i]);
    }
    free(lines);

    return config;
}

const char *get_config_value(t_config *config, const char *key)
{
    t_config_entry *entry = config->entries;

    while (entry)
    {
        if (ft_strcmp(entry->key, key) == 0)
            return entry->value;
        entry = entry->next;
    }

    return NULL;
}

3.7 パフォーマンス最適化とベンチマーク

3.7.1 文字列操作のコスト

#include <time.h>

void benchmark_string_functions()
{
    const int iterations = 1000000;
    clock_t start, end;

    // テスト文字列
    char *test_short = "Hello";
    char *test_medium = "The quick brown fox jumps over the lazy dog";
    char *test_long = malloc(10001);
    memset(test_long, 'A', 10000);
    test_long[10000] = '\0';

    printf("Benchmarking ft_strlen:\n");

    // 短い文字列
    start = clock();
    for (int i = 0; i < iterations; i++)
        ft_strlen(test_short);
    end = clock();
    printf("  Short (%zu chars): %.3f ms\n",
           ft_strlen(test_short),
           ((double)(end - start) / CLOCKS_PER_SEC) * 1000);

    // 中程度の文字列
    start = clock();
    for (int i = 0; i < iterations; i++)
        ft_strlen(test_medium);
    end = clock();
    printf("  Medium (%zu chars): %.3f ms\n",
           ft_strlen(test_medium),
           ((double)(end - start) / CLOCKS_PER_SEC) * 1000);

    // 長い文字列
    start = clock();
    for (int i = 0; i < iterations; i++)
        ft_strlen(test_long);
    end = clock();
    printf("  Long (%zu chars): %.3f ms\n",
           ft_strlen(test_long),
           ((double)(end - start) / CLOCKS_PER_SEC) * 1000);

    free(test_long);
}

3.7.2 キャッシュ効率

void measure_cache_effects()
{
    // L1キャッシュ: 通常32KB
    // L2キャッシュ: 通常256KB-1MB
    // L3キャッシュ: 通常8MB-32MB

    size_t sizes[] = {
        1024,       // 1KB - L1に収まる
        16384,      // 16KB - L1に収まる
        65536,      // 64KB - L1を超える
        262144,     // 256KB - L2に収まる
        1048576,    // 1MB - L2を超える
        4194304,    // 4MB - L3に収まる
        16777216    // 16MB - L3を超える可能性
    };

    for (int s = 0; s < sizeof(sizes)/sizeof(sizes[0]); s++)
    {
        size_t size = sizes[s];
        char *buffer = malloc(size);
        memset(buffer, 'A', size - 1);
        buffer[size - 1] = '\0';

        // ウォームアップ
        for (int i = 0; i < 10; i++)
            ft_strlen(buffer);

        // 計測
        clock_t start = clock();
        for (int i = 0; i < 1000; i++)
            ft_strlen(buffer);
        clock_t end = clock();

        double time_per_call = ((double)(end - start) / CLOCKS_PER_SEC) / 1000 * 1e9;
        double ns_per_byte = time_per_call / size;

        printf("Buffer %zu bytes: %.2f ns/call, %.3f ns/byte\n",
               size, time_per_call, ns_per_byte);

        free(buffer);
    }
}

3.8 セキュリティとベストプラクティス

3.8.1 安全な文字列操作のガイドライン

// 1. 常にバッファサイズを追跡する
typedef struct s_safe_string {
    char *data;
    size_t length;
    size_t capacity;
} t_safe_string;

t_safe_string *safe_string_new(size_t initial_capacity)
{
    t_safe_string *s = malloc(sizeof(t_safe_string));
    if (!s)
        return NULL;

    s->data = malloc(initial_capacity);
    if (!s->data)
    {
        free(s);
        return NULL;
    }

    s->data[0] = '\0';
    s->length = 0;
    s->capacity = initial_capacity;

    return s;
}

int safe_string_append(t_safe_string *s, const char *str)
{
    size_t str_len = ft_strlen(str);

    // 容量チェックと拡張
    if (s->length + str_len + 1 > s->capacity)
    {
        size_t new_capacity = (s->length + str_len + 1) * 2;
        char *new_data = realloc(s->data, new_capacity);
        if (!new_data)
            return -1;

        s->data = new_data;
        s->capacity = new_capacity;
    }

    // コピー
    ft_strlcpy(s->data + s->length, str, s->capacity - s->length);
    s->length += str_len;

    return 0;
}

// 2. 入力のサニタイズ
char *sanitize_string(const char *input, const char *allowed_chars)
{
    size_t len = ft_strlen(input);
    char *result = malloc(len + 1);
    size_t j = 0;

    if (!result)
        return NULL;

    for (size_t i = 0; i < len; i++)
    {
        if (ft_strchr(allowed_chars, input[i]))
            result[j++] = input[i];
    }

    result[j] = '\0';
    return result;
}

3.8.2 よくある脆弱性パターンと対策

// 脆弱なパターン1: フォーマット文字列攻撃
void vulnerable_log(char *user_input)
{
    printf(user_input);  // 危険！
}

void safe_log(char *user_input)
{
    printf("%s", user_input);  // 安全
}

// 脆弱なパターン2: 境界チェックなしのコピー
void vulnerable_copy(char *dest, char *src)
{
    while (*src)
        *dest++ = *src++;
    *dest = '\0';
}

void safe_copy(char *dest, size_t dest_size, const char *src)
{
    ft_strlcpy(dest, src, dest_size);
}

// 脆弱なパターン3: オフバイワンエラー
void off_by_one_error(char *buffer, size_t size)
{
    for (size_t i = 0; i <= size; i++)  // <= ではなく < を使うべき
        buffer[i] = 'A';
}

3.9 本章のまとめ

3.9.1 学習した理論

• 形式言語理論

• 文字列アルゴリズム

• C言語の文字列

3.9.2 実装したLibft関数

| 関数 | 用途 | 計算量 | |------|------|--------| | ft_strlen | 文字列長 | O(n) | | ft_strcpy | コピー（危険） | O(n) | | ft_strlcpy | 安全なコピー | O(n) | | ft_strcat | 連結（危険） | O(n+m) | | ft_strlcat | 安全な連結 | O(n+m) | | ft_strcmp | 比較 | O(n) | | ft_strncmp | n文字比較 | O(n) | | ft_strchr | 文字検索 | O(n) | | ft_strrchr | 逆方向検索 | O(n) | | ft_strnstr | 部分文字列検索 | O(nm) | | ft_strdup | 複製 | O(n) | | ft_substr | 部分文字列 | O(n) | | ft_strjoin | 結合 | O(n+m) | | ft_strtrim | トリム | O(n) | | ft_split | 分割 | O(n) | | ft_itoa | 整数→文字列 | O(log n) | | ft_strmapi | マップ | O(n) | | ft_striteri | イテレート | O(n) |

3.9.3 次のステップ

次章では、メモリ操作関数を学びます：

• メモリ階層とキャッシュの仕組み
• 仮想メモリとページング
• ポインタの深い理解
• ft_memset, ft_bzero, ft_memcpy, ft_memmove の実装

文字列操作とメモリ操作は密接に関連しており、両方の理解がより効率的で安全なコードを書く基礎となります。

3.2 文字列アルゴリズムの歴史と理論

3.2.1 文字列探索問題の定義

文字列探索（String Searching/Pattern Matching）問題は、コンピュータサイエンスで最も基本的かつ重要な問題の一つです。

問題の定式化

___CODE_BLOCK_14___

応用分野

3.2.2 ナイーブアルゴリズム（Brute Force）

最も単純なアプローチから始めましょう。

___CODE_BLOCK_15___

計算量分析

• 平均ケース: O(n)

3.2.3 Knuth-Morris-Pratt（KMP）アルゴリズム

1977年、ドナルド・クヌース（Donald Knuth）、ジェームズ・モリス（James Morris）、ヴォーン・プラット（Vaughan Pratt）が独立に発見し、共同で発表した画期的なアルゴリズムです。

核心的なアイデア

ミスマッチが発生したとき、すでに比較した情報を活用して、無駄な比較をスキップします。

___CODE_BLOCK_16___

失敗関数（Failure Function）の計算

失敗関数 π[j] は、pattern[0..j] の最長の「真の接頭辞かつ接尾辞」の長さを表します。

___CODE_BLOCK_17___

KMPアルゴリズムの完全実装

___CODE_BLOCK_18___

計算量

• 前処理（失敗関数）: O(m)
• 検索: O(n)
• 合計: O(n + m)

3.2.4 Boyer-Moore アルゴリズム

1977年、ロバート・ボイヤー（Robert Boyer）とJ・ストロザー・ムーア（J Strother Moore）が発表した、実用上最も高速な文字列検索アルゴリズムの一つです。

革新的なアイデア

• 後ろから比較: パターンを右から左に比較する
• Bad Character Rule: ミスマッチ文字を利用してスキップ
• Good Suffix Rule: マッチした部分を利用してスキップ

___CODE_BLOCK_19___

Bad Character Rule の実装

___CODE_BLOCK_20___

Good Suffix Rule の実装

___CODE_BLOCK_21___

Boyer-Moore 完全実装

___CODE_BLOCK_22___

計算量

• 前処理: O(m + |Σ|)
• 最悪ケース: O(nm)
• 平均・最良ケース: O(n/m) - サブリニア！

3.2.5 Rabin-Karp アルゴリズム

1987年、マイケル・ラビン（Michael Rabin）とリチャード・カープ（Richard Karp）が発表した、ハッシュ関数を利用したアルゴリズムです。

アイデア

パターンのハッシュ値を計算し、テキストの各位置のハッシュ値と比較します。ローリングハッシュ（Rolling Hash）により、効率的に次の位置のハッシュを計算できます。

ローリングハッシュ

___CODE_BLOCK_23___

実装

___CODE_BLOCK_24___

複数パターン検索

Rabin-Karpの真価は、複数のパターンを同時に検索する場合に発揮されます。

___CODE_BLOCK_25___

3.2.6 Aho-Corasick アルゴリズム

1975年、アルフレッド・エイホ（Alfred Aho）とマーガレット・コラシック（Margaret Corasick）が発表した、複数パターン同時検索アルゴリズムです。

構造

• トライ（Trie）: パターンの共通接頭辞を共有する木構造
• 失敗リンク: KMPの失敗関数を多パターンに一般化
• 出力リンク: マッチしたパターンを報告

___CODE_BLOCK_26___

計算量

• 前処理: O(Σ|patterns|)
• 検索: O(n + k) (kはマッチ数)

3.2.7 Suffix Array と LCP Array

接尾辞配列は、テキストの全ての接尾辞を辞書順にソートした配列です。1990年代に開発され、バイオインフォマティクスで広く使用されています。

定義

___CODE_BLOCK_27___

LCP配列（Longest Common Prefix）

隣接する接尾辞の最長共通接頭辞の長さです。

___CODE_BLOCK_28___

実装（SA-IS法の簡易版）

___CODE_BLOCK_29___

3.3 C言語における文字列の本質

3.3.1 文字列リテラルとメモリ配置

C言語の文字列は、他の高級言語とは根本的に異なります。文字列型は存在せず、「ヌル文字で終端される文字の配列」として実装されます。

文字列リテラルのメモリ配置

___CODE_BLOCK_30___

プロセスのメモリレイアウト

___CODE_BLOCK_31___

3.3.2 ヌル終端の歴史と設計判断

なぜC言語はヌル終端を採用したのでしょうか？

1970年代のコンテキスト

• メモリの希少性: 文字列長を別途保存するのは贅沢だった
• PDP-11 アーキテクチャ: ヌルチェックが効率的
• UNIXとの親和性: ファイル名など、可変長文字列が必要

ヌル終端 vs 長さプレフィックス

___CODE_BLOCK_32___

ヌル終端の利点と欠点

利点：

• メモリ効率（追加のメタデータ不要）
• 任意の長さの文字列
• シンプルなAPI

欠点：

• 長さ取得がO(n)
• バッファオーバーフローのリスク
• バイナリデータに0x00を含められない

3.3.3 文字列操作の危険性

バッファオーバーフローの歴史

1988年のMorris Wormは、fingerdプログラムのgets()関数を悪用しました。これは最初の大規模なインターネットワームでした。

___CODE_BLOCK_33___

2003年のSQL Slammer

SQL Serverのスタックバッファオーバーフローを悪用し、わずか10分で75,000台以上のサーバーに感染しました。

現代の防御機構

• スタックカナリア: バッファとリターンアドレスの間に検知用の値を配置
• ASLR: アドレス空間のランダム化
• NX/DEP: スタック上のコード実行禁止
• SSP: スタック破壊検出

___CODE_BLOCK_34___

3.4 Libft文字列関数の実装

3.4.1 ft_strlen - 文字列長の測定

これまで学んだ理論を基に、実際の実装に入りましょう。

基本実装

___CODE_BLOCK_35___

なぜsize_tを使うのか

___CODE_BLOCK_36___

ポインタ演算版

___CODE_BLOCK_37___

最適化版（ワード単位処理）

現代のCPUは一度に複数バイトを処理できます。この特性を活用した最適化です。

___CODE_BLOCK_38___

3.4.2 ft_strcpy / ft_strlcpy - 文字列コピー

ft_strcpy（危険な関数）

___CODE_BLOCK_39___

ft_strlcpy（安全な代替）

OpenBSDで開発された、より安全な文字列コピー関数です。

___CODE_BLOCK_40___

使用例と安全性

___CODE_BLOCK_41___

3.4.3 ft_strcat / ft_strlcat - 文字列連結

ft_strcat（危険な関数）

___CODE_BLOCK_42___

ft_strlcat（安全な代替）

___CODE_BLOCK_43___

3.4.4 ft_strcmp / ft_strncmp - 文字列比較

ft_strcmp

___CODE_BLOCK_44___

なぜunsigned charにキャストするのか

___CODE_BLOCK_45___

ft_strncmp

___CODE_BLOCK_46___

3.4.5 ft_strchr / ft_strrchr - 文字検索

ft_strchr

___CODE_BLOCK_47___

ft_strrchr

___CODE_BLOCK_48___

3.4.6 ft_strnstr - 部分文字列検索

___CODE_BLOCK_49___

3.4.7 ft_strdup - 文字列複製

___CODE_BLOCK_50___

3.5 追加の文字列関数

3.5.1 ft_substr - 部分文字列抽出

___CODE_BLOCK_51___

3.5.2 ft_strjoin - 文字列結合

___CODE_BLOCK_52___

3.5.3 ft_strtrim - 文字列トリム

___CODE_BLOCK_53___

3.5.4 ft_split - 文字列分割

___CODE_BLOCK_54___

3.5.5 ft_itoa - 整数から文字列への変換

___CODE_BLOCK_55___

3.5.6 ft_strmapi - 文字列変換

___CODE_BLOCK_56___

3.5.7 ft_striteri - 文字列反復処理

___CODE_BLOCK_57___

3.6 実践的なアプリケーション

3.6.1 簡易的なシェルのコマンドパーサー

___CODE_BLOCK_58___

3.6.2 URLパーサー

___CODE_BLOCK_59___

3.6.3 設定ファイルパーサー

___CODE_BLOCK_60___

3.7 パフォーマンス最適化とベンチマーク

3.7.1 文字列操作のコスト

___CODE_BLOCK_61___

3.7.2 キャッシュ効率

___CODE_BLOCK_62___

3.8 セキュリティとベストプラクティス

3.8.1 安全な文字列操作のガイドライン

___CODE_BLOCK_63___

3.8.2 よくある脆弱性パターンと対策

___CODE_BLOCK_64___

3.9 本章のまとめ

3.9.1 学習した理論

• 形式言語理論

• 文字列アルゴリズム

• C言語の文字列

3.9.2 実装したLibft関数

| 関数 | 用途 | 計算量 | |------|------|--------| | ft_strlen | 文字列長 | O(n) | | ft_strcpy | コピー（危険） | O(n) | | ft_strlcpy | 安全なコピー | O(n) | | ft_strcat | 連結（危険） | O(n+m) | | ft_strlcat | 安全な連結 | O(n+m) | | ft_strcmp | 比較 | O(n) | | ft_strncmp | n文字比較 | O(n) | | ft_strchr | 文字検索 | O(n) | | ft_strrchr | 逆方向検索 | O(n) | | ft_strnstr | 部分文字列検索 | O(nm) | | ft_strdup | 複製 | O(n) | | ft_substr | 部分文字列 | O(n) | | ft_strjoin | 結合 | O(n+m) | | ft_strtrim | トリム | O(n) | | ft_split | 分割 | O(n) | | ft_itoa | 整数→文字列 | O(log n) | | ft_strmapi | マップ | O(n) | | ft_striteri | イテレート | O(n) |

3.9.3 次のステップ

次章では、メモリ操作関数を学びます：

• メモリ階層とキャッシュの仕組み
• 仮想メモリとページング
• ポインタの深い理解
• ft_memset, ft_bzero, ft_memcpy, ft_memmove の実装

文字列操作とメモリ操作は密接に関連しており、両方の理解がより効率的で安全なコードを書く基礎となります。