60、strstr 的实现：如何在一个字符串中查找子串？

字符串查找，说白了就是在一个大串里找一个小串。C标准库里的strstr函数干的就是这个活。我当年刚入行时，觉得这玩意儿不就是个循环比对嘛，有啥难的？直到有一次在嵌入式项目里，因为自己手写的查找函数效率太低，导致整个通信协议栈响应超时……嗯，从那以后我再也不敢小看这个函数了。

一、strstr 到底是干什么的？

strstr的原型长这样：

char *strstr(const char *haystack, const char *needle);

它在haystack（干草堆）里找needle（针）。找到了，返回第一次出现的位置指针；没找到，返回NULL。就这么简单。

举个例子：

char str[] = "hello world";
char *p = strstr(str, "world");
if (p) {
    printf("找到了：%s\n", p);  // 输出 "world"
}

这里返回的是str中'w'的地址，所以打印出来是从world开始的剩余字符串。

二、最朴素的实现——暴力匹配

我个人习惯先从最直观的方式入手。暴力匹配的思路就是：从主串的每个位置开始，逐个字符去比较子串。

char *my_strstr(const char *str, const char *sub) {
    if (*sub == '\0') return (char *)str;  // 空子串，返回原串
    
    while (*str) {
        const char *s = str;
        const char *t = sub;
        
        while (*s && *t && (*s == *t)) {
            s++;
            t++;
        }
        
        if (*t == '\0') return (char *)str;  // 子串匹配完成
        str++;
    }
    
    return NULL;
}

这段代码的逻辑很直白：外层循环遍历主串的每个字符作为起点，内层循环逐个比对。一旦发现不匹配，就跳出内层循环，主串指针后移一位继续。

注意：这里有个容易踩的坑——空子串的处理。标准strstr规定，如果needle是空串，返回haystack本身。很多新手会忽略这个边界条件，直接返回NULL，那就错了。

三、暴力匹配的问题在哪？

你想想看，如果主串是"aaaaaaaaaaaaaaaaab"，子串是"aaaaab"，暴力匹配会怎么干？

它会从第一个'a'开始，比对到第6个字符发现是'a'不是'b'，失败。然后从第二个'a'开始，又比对到第7个字符……每次都要回溯到子串的开头。最坏情况下，时间复杂度是O(n*m)，n是主串长度，m是子串长度。

我在项目中遇到过这种情况：一个几百字节的报文里查找一个模式串，暴力匹配跑了十几毫秒。在桌面应用上这不算啥，但在嵌入式系统里，这个时间足够让看门狗超时复位了。

四、KMP算法——让匹配不再回溯

KMP算法的核心思想是：当匹配失败时，主串指针不回溯，只移动子串指针。它通过一个next数组，记录了子串中每个位置之前的最长相同前后缀长度。

说白了，就是利用已经匹配过的信息，跳过那些不可能匹配的位置。

先看next数组的计算：

void get_next(const char *sub, int *next) {
    int len = strlen(sub);
    next[0] = -1;
    int i = 0, j = -1;
    
    while (i < len - 1) {
        if (j == -1 || sub[i] == sub[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

然后是用next数组进行匹配：

char *my_strstr_kmp(const char *str, const char *sub) {
    if (*sub == '\0') return (char *)str;
    
    int n = strlen(str);
    int m = strlen(sub);
    int next[m];
    get_next(sub, next);
    
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || str[i] == sub[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    
    if (j == m) return (char *)(str + i - j);
    return NULL;
}
小技巧：KMP的next数组里，next[0] = -1这个设计很巧妙。当j == -1时，表示子串第一个字符就不匹配，此时主串和子串指针都前进一位。这样就不用单独处理边界情况了。

五、两种实现的对比

对比项 暴力匹配 KMP算法
时间复杂度 O(n*m) O(n+m)
空间复杂度 O(1) O(m)
实现难度 简单 中等
适用场景 短串、小数据量 长串、重复模式多

我个人建议：在嵌入式开发中，如果子串长度不超过10个字符，暴力匹配完全够用。但如果你的子串有几十个字符，或者主串有几千字节，那还是老老实实用KMP吧。

六、核心逻辑流程图

下面这张图展示了暴力匹配和KMP的核心差异：

strstr 两种实现方式对比 暴力匹配流程 从主串第 i 个位置开始 逐个字符比对子串 匹配失败？主串 i++ 回溯 回溯 KMP算法流程 从主串第 i 个位置开始 逐个字符比对子串 匹配失败？子串 j = next[j] 主串 i 不回溯，继续前进 关键区别：主串指针是否回溯

七、避坑指南

我曾经在调试一个串口通信程序时，发现strstr总是返回NULL，但明明子串就在那里。排查了半天，原来是主串末尾有个换行符'\n'，而子串里没有。这种问题在嵌入式开发中特别常见——从传感器或通信接口收到的数据，末尾往往带着不可见字符。

另外还有几个容易忽略的点：

  • 字符串必须以'\0'结尾——如果主串或子串不是合法的C字符串，strstr会越界访问，后果不可预测。
  • 子串长度不能超过主串——虽然标准实现会返回NULL，但如果你自己手写实现，别忘了加这个判断。
  • 大小写敏感——strstr是区分大小写的。如果需要忽略大小写，可以用strcasestr（POSIX扩展）或者自己写一个。
核心要点：
  • 暴力匹配简单直观，适合短串和小数据量
  • KMP算法通过next数组避免主串回溯，适合长串和重复模式
  • 空子串返回原串本身，这个边界条件别忘
  • 嵌入式开发中注意字符串末尾的不可见字符

好了，关于strstr的实现就聊到这儿。记住，没有最好的算法，只有最合适的场景。下次你在代码里写字符串查找时，不妨想想：这个场景值得上KMP吗？

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →