题目要求

给出两个字符串 str1 和 str2 ，请你在 str1 字符串中找出 str2 字符串的第一个匹配项的下标（下标从 0 开始）。如果 str2 不是 str1 的一部分，则返回 -1 。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 构建KMP算法中的next数组
void getNext(const char *pattern, int *next, int len) {
    next[0] = 0; // 初始位置的最长公共前后缀长度为0
    int j = 0; // 前缀指针
    for (int i = 1; i < len; ++i) { // 后缀指针从1开始遍历
        // 当字符不匹配时，回溯到前一个位置的最长公共前后缀位置
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        // 字符匹配，公共前后缀长度增加
        if (pattern[i] == pattern[j]) {
            ++j;
        }
        next[i] = j; // 记录当前位置的最长公共前后缀长度
    }
}

int strStr(const char *str1, const char *str2) {
    int n = strlen(str1);
    int m = strlen(str2);
    
    // 处理边界情况
    if (m == 0) return 0; // 空字符串的特殊处理
    if (n < m) return -1; // 模式串比主串长
    
    int *next = (int *)malloc(m * sizeof(int));
    getNext(str2, next, m); // 预处理生成next数组
    
    int j = 0; // 模式串指针
    for (int i = 0; i < n; ) { // 主串指针i不回溯
        if (str1[i] == str2[j]) { // 当前字符匹配成功
            ++i;
            ++j;
            if (j == m) { // 完全匹配模式串
                free(next);
                return i - m; // 返回起始位置
            }
        } else {
            if (j > 0) {
                j = next[j - 1]; // 根据next数组跳转
            } else {
                ++i; // 模式串第一个字符就不匹配，主串后移
            }
        }
    }
    
    free(next);
    return -1; // 未找到匹配项
}

// 示例测试代码
int main() {
    const char *str1 = "hello";
    const char *str2 = "ll";
    printf("Test 1: %d\n", strStr(str1, str2)); // 应输出2

    str1 = "abababc";
    str2 = "ababc";
    printf("Test 2: %d\n", strStr(str1, str2)); // 应输出2

    str1 = "aaaaab";
    str2 = "aab";
    printf("Test 3: %d\n", strStr(str1, str2)); // 应输出3

    str1 = "abcde";
    str2 = "fgh";
    printf("Test 4: %d\n", strStr(str1, str2)); // 应输出-1

    return 0;
}

设计说明

1. KMP算法核心思想：通过预处理模式串生成next数组，记录匹配失败时的跳转位置，避免主串指针回退，实现高效匹配。
2. next数组构建：利用模式串自身的前后缀信息，确定每个位置的最长公共前后缀长度，用于匹配失败时的快速跳转。
3. 时间复杂度：预处理阶段O(m)，匹配阶段O(n)，整体O(n+m)，显著优于暴力法的O(n*m)。
4. 空间复杂度：需要O(m)的额外空间存储next数组。

算法优缺点分析

优点：

• 线性时间复杂度，适合处理大规模字符串。
• 避免主串指针回退，保证高效匹配。

缺点：

• 需要额外空间存储next数组。
• 实现逻辑相对复杂，调试难度较高。