跳到主要内容

找出字符串中第一个匹配项的下标

· 阅读需 8 分钟
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——28题​

💡 参考代码：​

/**
 * 在haystack字符串中查找needle字符串的第一个匹配位置
 * @param haystack 主字符串
 * @param needle 要查找的子字符串
 * @return 返回第一次匹配的索引，如果未找到则返回-1
 */
int strStr(char* haystack, char* needle) {
    // 边界条件处理
    if (needle == NULL || *needle == '\0') {
        return 0;  // 空字符串在任何字符串的索引0处匹配
    }
    
    if (haystack == NULL || *haystack == '\0') {
        return -1; // 主字符串为空但要查找的字符串非空，返回-1
    }
    
    int hLen = strlen(haystack);  // 主字符串长度
    int nLen = strlen(needle);    // 子字符串长度
    
    // 如果子字符串比主字符串长，不可能匹配
    if (nLen > hLen) {
        return -1;
    }
    
    // 构建next数组（KMP算法的核心）
    int* next = (int*)malloc(sizeof(int) * nLen);
    next[0] = 0;  // 第一个字符的最长相等前后缀长度为0
    int j = 0;    // 前缀末尾索引
    
    // 构造next数组
    for (int i = 1; i < nLen; i++) {
        // 当前后缀不匹配时，回退到前一个位置的next值
        while (j > 0 && needle[i] != needle[j]) {
            j = next[j - 1];
        }
        // 如果当前字符匹配，前缀长度加1
        if (needle[i] == needle[j]) {
            j++;
        }
        next[i] = j;  // 记录当前位置的最长相等前后缀长度
    }
    
    // KMP匹配过程
    j = 0;  // needle的索引
    for (int i = 0; i < hLen; i++) {
        // 当字符不匹配时，根据next数组回退
        while (j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1];
        }
        // 如果字符匹配，移动needle的指针
        if (haystack[i] == needle[j]) {
            j++;
        }
        // 如果needle已经完全匹配，返回匹配起始位置
        if (j == nLen) {
            free(next);  // 释放内存
            return i - nLen + 1;
        }
    }
    
    free(next);  // 释放内存
    return -1;   // 未找到匹配
}

📖 总结：​

点击展开题目总结

🤔 找出字符串中第一个匹配项的下标

1️⃣ 题目核心信息​

🎯 功能描述：在主字符串(haystack)中查找子字符串(needle)第一次出现的位置，若不存在则返回-1

📥 输入输出：

  • 输入：
    • haystack：主字符串，被搜索的字符串
    • needle：模式字符串，需要查找的子字符串
  • 输出：返回needle在haystack中第一次出现的索引位置，如果不存在则返回-1

2️⃣ 实现原理​

💡 核心思路：使用KMP(Knuth-Morris-Pratt)字符串匹配算法，通过预处理模式串构建next数组来避免不必要的字符比较

📋 实现步骤：

  1. 处理边界情况：空字符串、主串为空等情况
  2. 构建next数组：记录模式串中每个位置的最长相等前后缀长度
  3. 使用KMP算法进行匹配：利用next数组避免主串指针回溯
  4. 返回匹配结果：找到匹配则返回起始位置，否则返回-1

3️⃣ 关键点解析​

🎯 代码技巧​

  • KMP算法应用：通过构建next数组实现高效的字符串匹配
  • 双指针技术：使用两个指针分别遍历主串和模式串
  • 状态回退优化：利用next数组实现匹配失败时的智能回退，避免重复比较

4️⃣ 使用场景​

✅ 适用情况：​

  • 在大文本中查找特定子串的位置
  • 需要高效字符串匹配的场景
  • 文本编辑器的查找功能实现

⚠️ 前提条件：​

  • 输入参数为有效的C风格字符串
  • 字符串以'\0'结尾

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(n + m)，其中n是主串长度，m是模式串长度，避免了暴力算法的O(n*m)复杂度

  • 💾 空间复杂度：O(m)，主要用于存储next数组

6️⃣ 注意事项​

🚩 边界情况：​

  • needle为空字符串时应返回0
  • haystack为空字符串但needle非空时应返回-1
  • needle长度大于haystack时直接返回-1

💥 易错点：​

  • next数组的构建逻辑容易出错，特别是回退条件的判断
  • 匹配成功后的返回索引计算容易错误，应返回i - nLen + 1
  • 内存管理需要注意，使用完next数组后需要释放内存

7️⃣ 注意事项​

KMP算法原理简述​

KMP算法是一种改进的字符串匹配算法，它的核心思想是当字符匹配失败时，利用已经匹配的部分信息，尽可能地跳过一些不必要的比较。

第一步：边界条件处理​

if (needle == NULL || *needle == '\0') {
    return 0;  // 空字符串在任何字符串的索引0处匹配
}

if (haystack == NULL || *haystack == '\0') {
    return -1; // 主字符串为空但要查找的字符串非空，返回-1
}

这部分处理特殊情况：

  • 如果要查找的字符串为空，则在任何字符串的第0个位置都能找到它
  • 如果主字符串为空但要查找的字符串不为空，则肯定找不到

第二步：获取字符串长度并比较​

int hLen = strlen(haystack);  // 主字符串长度
int nLen = strlen(needle);    // 子字符串长度

if (nLen > hLen) {
    return -1;
}

如果要查找的字符串比主字符串还长，那肯定找不到。

第三步：构建next数组（KMP算法的核心）​

int* next = (int*)malloc(sizeof(int) * nLen);
next[0] = 0;  // 第一个字符的最长相等前后缀长度为0
int j = 0;    // 前缀末尾索引

// 构造next数组
for (int i = 1; i < nLen; i++) {
    // 当前后缀不匹配时，回退到前一个位置的next值
    while (j > 0 && needle[i] != needle[j]) {
        j = next[j - 1];
    }
    // 如果当前字符匹配，前缀长度加1
    if (needle[i] == needle[j]) {
        j++;
    }
    next[i] = j;  // 记录当前位置的最长相等前后缀长度
}

我们通过一个具体例子来理解next数组的构建过程。假设needle = "ababa"：

ineedle[i]jnext[i]说明
0a00初始值
1b00'a' != 'b'，j保持0
2a11'b' != 'a'，j回退到next[0]=0，然后'a' == 'a'，j=1
3b22'a' != 'b'，j回退到next[1]=0，然后'b' == 'b'，j=1，再'a' == 'a'，j=2
4a33同上逻辑，j=3

所以next = [0, 0, 1, 2, 3]

第四步：KMP匹配过程​

j = 0;  // needle的索引
for (int i = 0; i < hLen; i++) {
    // 当字符不匹配时，根据next数组回退
    while (j > 0 && haystack[i] != needle[j]) {
        j = next[j - 1];
    }
    // 如果字符匹配，移动needle的指针
    if (haystack[i] == needle[j]) {
        j++;
    }
    // 如果needle已经完全匹配，返回匹配起始位置
    if (j == nLen) {
        free(next);
        return i - nLen + 1;
    }
}

示例1：haystack = "sadbutsad", needle = "sad"

首先构建的next数组为[0, 0, 0]（因为"sad"中没有重复的前后缀）

ihaystack[i]jneedle[j]匹配情况说明
0s0s匹配j++ → 1
1a1a匹配j++ → 2
2d2d匹配j++ → 3
--3--j==nLen，匹配成功，返回 2-3+1=0

所以返回索引0。

示例2：haystack = "leetcode", needle = "leeto"

构建的next数组为[0, 0, 0, 0, 0]（因为"leeto"中没有重复前后缀）

ihaystack[i]jneedle[j]匹配情况说明
0l0l匹配j++ → 1
1e1e匹配j++ → 2
2e2e匹配j++ → 3
3t3t匹配j++ → 4
4c4o不匹配j回退到next[3]=0，仍不匹配，j保持0
5o0l不匹配j保持0
6d0l不匹配j保持0
7e0l不匹配j保持0

整个过程j从未达到nLen=5，所以返回-1。

KMP算法的优势​

相比暴力匹配算法，KMP算法的优势在于：

1.时间复杂度从O(n*m)降低到O(n+m)

2.当发生不匹配时，主串的指针不会回溯，避免了重复比较

3.利用已匹配的信息，通过next数组决定模式串应该移动多少位

这就是KMP算法解决字符串匹配问题的完整过程。

这个 KMP算法 我至今不理解！（20250816）

加载评论中...