BB3-判断子串s2是否在母串s1中匹配，返回第一个匹配位置的索引

代码实现

/**
 * 判断子串s2是否在母串s1中匹配，返回第一个匹配位置的索引
 * @param s1 母串（被搜索的字符串）
 * @param s2 子串（要搜索的字符串）
 * @return 匹配成功返回第一个匹配字符的索引，失败返回-1
 */
int find(char s1[], char s2[]) {
    // 边界条件检查
    if (s1 == NULL || s2 == NULL) {
        return -1;
    }

    // 空子串处理：空串在任何字符串中都匹配，位置为0
    if (s2[0] == '\0') {
        return 0;
    }

    // 从母串的每个位置开始尝试匹配
    int pos = 0;  // 当前尝试匹配的起始位置

    while (s1[pos] != '\0') {  // 遍历母串的每个可能起始位置
        int p1 = pos;  // 母串当前比较位置
        int p2 = 0;    // 子串当前比较位置

        // 在当前位置尝试匹配整个子串
        while (s1[p1] != '\0' && s2[p2] != '\0') {
            if (s1[p1] == s2[p2]) {
                // 字符匹配，继续比较下一个字符
                p1++;
                p2++;
            } else {
                // 字符不匹配，跳出内层循环
                break;
            }
        }

        // 检查是否完全匹配
        if (s2[p2] == '\0') {
            // 子串已完全匹配，返回匹配起始位置
            return pos;
        }

        // 当前位置匹配失败，尝试下一个起始位置
        pos++;
    }

    // 遍历完所有可能位置都未找到匹配
    return -1;
}

/**
 * 优化版本1：添加长度预检查
 * @param s1 母串
 * @param s2 子串
 * @return 匹配成功返回索引，失败返回-1
 */
int find_optimized(char s1[], char s2[]) {
    if (s1 == NULL || s2 == NULL) {
        return -1;
    }

    if (s2[0] == '\0') {
        return 0;
    }

    int len1 = strlen(s1);
    int len2 = strlen(s2);

    // 如果子串比母串长，不可能匹配
    if (len2 > len1) {
        return -1;
    }

    // 只需要检查到 len1 - len2 的位置
    for (int pos = 0; pos <= len1 - len2; pos++) {
        int p1 = pos;
        int p2 = 0;

        // 尝试匹配
        while (s1[p1] != '\0' && s2[p2] != '\0' && s1[p1] == s2[p2]) {
            p1++;
            p2++;
        }

        // 检查是否完全匹配
        if (s2[p2] == '\0') {
            return pos;
        }
    }

    return -1;
}

朴素字符串匹配算法（Brute Force）

/**
 * 朴素字符串匹配算法（Brute Force）
 * @param text 母串（文本）
 * @param pattern 子串（模式串）
 * @return 匹配成功返回索引，失败返回-1
 */
int brute_force_match(char text[], char pattern[]) {
    if (text == NULL || pattern == NULL) {
        return -1;
    }

    int text_len = strlen(text);
    int pattern_len = strlen(pattern);

    if (pattern_len == 0) {
        return 0;
    }

    if (pattern_len > text_len) {
        return -1;
    }

    // 朴素匹配算法
    for (int i = 0; i <= text_len - pattern_len; i++) {
        int j;
        // 检查从位置i开始是否匹配
        for (j = 0; j < pattern_len; j++) {
            if (text[i + j] != pattern[j]) {
                break;
            }
        }

        // 如果j等于pattern_len，说明完全匹配
        if (j == pattern_len) {
            return i;
        }
    }

    return -1;  // 未找到匹配
}

算法执行流程图解

匹配成功示例：

母串s1："abcdef"
子串s2："cde"

执行过程：
pos=0: a vs c → 不匹配，pos=1
pos=1: b vs c → 不匹配，pos=2
pos=2: c vs c → 匹配，p1=3, p2=1
       d vs d → 匹配，p1=4, p2=2
       e vs e → 匹配，p1=5, p2=3
       p2='\0' → 完全匹配，返回pos=2

匹配失败示例：

母串s1："abcdef"
子串s2："cfg"

执行过程：
pos=0: a vs c → 不匹配，pos=1
pos=1: b vs c → 不匹配，pos=2
pos=2: c vs c → 匹配，p1=3, p2=1
       d vs f → 不匹配，跳出
pos=3: d vs c → 不匹配，pos=4
pos=4: e vs c → 不匹配，pos=5
pos=5: f vs c → 不匹配，结束
返回-1

算法状态变化图解

母串："hello world"
子串："wor"

匹配过程：
pos=0: h≠w → 失败
pos=1: e≠w → 失败
pos=2: l≠w → 失败
pos=3: l≠w → 失败
pos=4: o≠w → 失败
pos=5: 空格≠w → 失败
pos=6: w=w → 继续
       o=o → 继续
       r=r → 继续
       '\0'='\0' → 成功，返回6

复杂度分析

时间复杂度：O(m×n)

• 最坏情况：O(m×n)，其中m是母串长度，n是子串长度
• 最好情况：O(m)，第一个字符就不匹配
• 平均情况：O(m×n)，但在实际应用中通常表现较好
• 举例：母串长度1000，子串长度10，最坏情况下需要比较10000次

空间复杂度：O(1)

• 辅助变量：只使用常数个变量（pos, p1, p2等）
• 无额外存储：不需要额外的数据结构
• 总体空间复杂度：O(1)

KMP算法（Knuth-Morris-Pratt）- 更高效的字符串匹配

/**
 * KMP算法（Knuth-Morris-Pratt）- 更高效的字符串匹配
 * 时间复杂度：O(m+n)
 */
int kmp_match(char text[], char pattern[]) {
    if (text == NULL || pattern == NULL) return -1;

    int text_len = strlen(text);
    int pattern_len = strlen(pattern);

    if (pattern_len == 0) return 0;
    if (pattern_len > text_len) return -1;

    // 计算next数组（部分匹配表）
    int next[pattern_len];
    next[0] = 0;
    int j = 0;

    for (int i = 1; i < pattern_len; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        next[i] = j;
    }

    // KMP匹配过程
    j = 0;
    for (int i = 0; i < text_len; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == pattern_len) {
            return i - j + 1;
        }
    }

    return -1;
}

Boyer-Moore算法 - 另一种高效的字符串匹配算法

/**
 * Boyer-Moore算法 - 另一种高效的字符串匹配算法
 */
int boyer_moore_match(char text[], char pattern[]) {
    // 实现较为复杂，这里给出基本框架
    if (text == NULL || pattern == NULL) return -1;

    int text_len = strlen(text);
    int pattern_len = strlen(pattern);

    if (pattern_len == 0) return 0;
    if (pattern_len > text_len) return -1;

    // 预处理：计算坏字符表和好后缀表
    // ...（省略具体实现）

    // 匹配过程
    // ...（省略具体实现）

    return -1;  // 简化版本
}

错误处理完善版本

/**
 * 安全版本：添加完整的错误处理和边界检查
 */
int find_safe(char s1[], char s2[]) {
    // 参数验证
    if (s1 == NULL) {
        printf("错误：母串为空指针\n");
        return -1;
    }

    if (s2 == NULL) {
        printf("错误：子串为空指针\n");
        return -1;
    }

    // 空子串处理
    if (s2[0] == '\0') {
        return 0;  // 空串在任何位置都匹配
    }

    int len1 = strlen(s1);
    int len2 = strlen(s2);

    // 长度检查
    if (len1 < 0 || len2 < 0) {
        printf("错误：字符串长度异常\n");
        return -1;
    }

    // 子串不能比母串长
    if (len2 > len1) {
        return -1;
    }

    // 匹配过程
    for (int pos = 0; pos <= len1 - len2; pos++) {
        int match = 1;  // 假设匹配成功

        for (int i = 0; i < len2; i++) {
            if (s1[pos + i] != s2[i]) {
                match = 0;  // 匹配失败
                break;
            }
        }

        if (match) {
            return pos;  // 返回匹配位置
        }
    }

    return -1;  // 未找到匹配
}

性能测试对比

/**
 * 性能测试函数
 */
void performance_comparison() {
    char text[10000];
    char pattern[] = "search";

    // 构造测试文本
    for (int i = 0; i < 9990; i++) {
        text[i] = 'a' + (i % 26);
    }
    strcpy(text + 5000, "search");
    text[9999] = '\0';

    clock_t start, end;

    // 测试朴素算法
    start = clock();
    for (int i = 0; i < 10000; i++) {
        find(text, pattern);
    }
    end = clock();
    printf("朴素算法耗时: %ld\n", end - start);

    // 测试KMP算法
    start = clock();
    for (int i = 0; i < 10000; i++) {
        kmp_match(text, pattern);
    }
    end = clock();
    printf("KMP算法耗时: %ld\n", end - start);
}

实际应用示例

/**
 * 实用函数：在文件中搜索关键词
 */
int search_in_file(const char* filename, const char* keyword) {
    FILE* file = fopen(filename, "r");
    if (file == NULL) {
        printf("无法打开文件: %s\n", filename);
        return -1;
    }

    char line[1000];
    int line_number = 0;

    while (fgets(line, sizeof(line), file) != NULL) {
        line_number++;
        if (find(line, keyword) != -1) {
            printf("在第%d行找到关键词: %s", line_number, line);
            fclose(file);
            return line_number;
        }
    }

    fclose(file);
    return -1;  // 未找到
}

/**
 * 多个子串搜索
 */
int find_multiple(char s1[], char patterns[][100], int pattern_count) {
    for (int i = 0; i < pattern_count; i++) {
        int pos = find(s1, patterns[i]);
        if (pos != -1) {
            printf("找到模式串 '%s' 在位置 %d\n", patterns[i], pos);
            return pos;
        }
    }
    return -1;
}

算法特点

核心思想： 在母串的每个可能位置尝试匹配整个子串，一旦发现不匹配就移动到下一个位置重新开始。

关键技术： 1. 双重循环：外层遍历母串起始位置，内层进行字符匹配 2. 提前终止：发现不匹配立即跳出内层循环 3. 边界处理：正确处理字符串边界和空串情况

优势： - 实现简单：逻辑清晰，易于理解和实现 - 正确性高：算法简单，不容易出错 - 适用广泛：适用于各种字符集和长度的字符串

局限性： - 效率较低：最坏情况下时间复杂度为O(m×n) - 重复比较：可能对同一字符进行多次比较

应用场景： - 文本编辑器的查找功能 - 搜索引擎的关键词匹配 - 生物信息学中的序列匹配 - 病毒扫描中的模式匹配 - 数据验证和过滤

算法改进方向： 1. KMP算法：避免重复比较，时间复杂度O(m+n) 2. Boyer-Moore算法：从右向左匹配，平均性能更好 3. Sunday算法：基于启发式规则跳过更多字符

朴素字符串匹配算法虽然效率不是最高，但因其简单性和可靠性，在实际应用中仍然广泛使用，特别是在子串较短或对性能要求不高的场景中。