串：BF算法（朴素的魔术匹配算法）

一、数据结构：SString 定长串

#define MAXLEN 255  // 假设最大长度为 255（可按需调整）
typedef struct {
    char ch[MAXLEN + 1];  // 存储字符串，下标从 1 开始（ch[1]~ch[MAXLEN]）
    int length;           // 字符串实际长度
} SString;

• 设计特点：
  • 数组 ch 长度是 MAXLEN + 1，下标从 1 开始（ch[0] 不用，方便和算法中的 “位置 1 起始” 逻辑对齐）。
  • length 记录字符串实际有效长度（比如 "abc" 的 length=3，ch[1]='a', ch[2]='b', ch[3]='c'）。

二、BF 算法完整代码（基于 SString）

#include <stdio.h>
#define MAXLEN 255

// 定义定长字符串结构
typedef struct {
    char ch[MAXLEN + 1];  // 下标 1~MAXLEN 存储字符
    int length;           // 字符串实际长度
} SString;

// BF 算法实现：从主串 S 的 pos 位置开始，查找模式串 T
// 返回：匹配的起始位置（从 1 开始计数），失败返回 0
int Index_BF(SString S, SString T, int pos) {
    int i = pos;  // 主串当前比较位置（从 pos 开始，pos≥1）
    int j = 1;    // 模式串当前比较位置（从 1 开始，j≥1）
    
    // 循环条件：主串和模式串都未比较到末尾
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[j]) {
            // 1. 字符匹配：继续比较下一个字符
            i++;
            j++;
        } else {
            // 2. 字符不匹配：主串回退，模式串重置
            i = i - j + 2;  // 主串回到“上一次起始位置 +1”
            j = 1;          // 模式串从头开始
        }
    }
    
    // 3. 匹配结果判断
    if (j > T.length) {
        // 模式串完全匹配（j 超出模式串长度）
        return i - T.length;  // 返回主串中匹配的起始位置
    } else {
        // 主串匹配完但模式串未匹配完
        return 0;
    }
}

int main() {
    // 初始化主串 S 和模式串 T
    SString S, T;
    
    // 主串 S: "ABCABDABCABC"（下标 1~11）
    S.ch[1] = 'A'; S.ch[2] = 'B'; S.ch[3] = 'C'; 
    S.ch[4] = 'A'; S.ch[5] = 'B'; S.ch[6] = 'D'; 
    S.ch[7] = 'A'; S.ch[8] = 'B'; S.ch[9] = 'C'; 
    S.ch[10] = 'A'; S.ch[11] = 'B'; S.ch[12] = 'C'; 
    S.length = 12;  // 实际长度
    
    // 模式串 T: "ABCABC"（下标 1~6）
    T.ch[1] = 'A'; T.ch[2] = 'B'; T.ch[3] = 'C'; 
    T.ch[4] = 'A'; T.ch[5] = 'B'; T.ch[6] = 'C'; 
    T.length = 6;   // 实际长度
    
    // 从 pos=1 开始匹配
    int result = Index_BF(S, T, 1);
    if (result != 0) {
        printf("匹配成功，起始位置：%d\n", result);
    } else {
        printf("匹配失败\n");
    }
    
    return 0;
}

三、代码逐行解析（核心逻辑）

1. 初始化与循环条件

int i = pos;  // 主串起始位置（pos≥1，对应 ch[pos]）
int j = 1;    // 模式串起始位置（固定从 1 开始）

// 循环条件：主串未到末尾（i ≤ S.length）且模式串未到末尾（j ≤ T.length）
while (i <= S.length && j <= T.length) {

• 关键：S.ch 和 T.ch 的下标从 1 开始（和日常习惯的 0 起始不同，需特别注意）。

2. 字符匹配与回退逻辑

if (S.ch[i] == T.ch[j]) {
    // 匹配：主串和模式串同时后移
    i++;
    j++;
} else {
    // 不匹配：主串回退到“上一次起始位置 +1”，模式串重置
    i = i - j + 2;  // 核心公式
    j = 1;
}

• 匹配成功：i 和 j 同时 +1，继续比较下一个字符。
• 匹配失败：主串回退到“上一次起始位置 +1”，模式串重置
  • 公式 i = (i - j + 1) + 1 

3. 匹配结果判断

if (j > T.length) {
    // 模式串全部匹配完成（j 超出模式串长度）
    return i - T.length;  // 返回主串中匹配的起始位置
} else {
    // 主串匹配完但模式串未匹配完
    return 0;
}

• 匹配成功：j 会从 1 走到 T.length + 1（因为 j++ 后超出模式串长度），此时 i - T.length 就是主串中匹配子串的起始位置。
• 例如：模式串长度 T.length=6，i 最终是 7 → 起始位置 7 - 6 = 1（表示主串从下标 1 开始匹配成功）。

四、关键细节：下标从 1 开始的影响

• 在这份代码中，字符串的位置从 1 开始计数（ch[1] 是第一个字符）。
• 因此，“返回 i - T.length” 的含义是：主串中匹配子串的起始位置（从 1 开始）。

五、BF 算法的优缺点（基于定长串）

优点：

1. 逻辑直观：适合教学和理解字符串匹配的核心思想。
2. 适配定长串：通过 length 字段和下标从 1 开始的设计，贴近教材中的经典实现。

缺点：

1. 效率问题：最坏时间复杂度 \(O(n \times m)\)（n 主串长度，m 模式串长度），重复回退导致效率低。
2. 空间浪费：ch[MAXLEN+1] 是定长数组，若字符串实际长度远小于 MAXLEN，会浪费空间。

七、总结

         教材经典 BF 算法 的实现，核心特点是：

• 基于定长数组 SString，下标从 1 开始。
• 通过 i（主串指针）和 j（模式串指针）的移动、回退实现匹配。

理解它的关键是：

1. 适应下标从 1 开始的设计（和日常代码习惯不同）。
2. 掌握回退公式 i = i - j + 2 的逻辑（让主串重新从 “上一次起始位置 +1” 开始匹配）。