C语言实现strstr：从BF暴力匹配到KMP算法详解
C语言中的 strstr 用于在字符串中查找子串。本文将展示如何利用 string.h 调用该函数，并分别通过 BF（暴力）算法和 KMP（改进）算法模拟实现其核心逻辑，解析指针回溯与 Next 数组的应用。
strstr 函数功能概述
strstr 是 C 标准库 <string.h> 中提供的字符串匹配函数。其核心作用是判断子串 str2 是否存在于主串 str1 中。若匹配成功，返回指向 str1 中首次出现 str2 起始位置的指针；若未找到，则返回空指针 NULL。
以下示例展示了基本用法：
#include <stdio.h>
#include <string.h>
int main(){
char* s1 = "abcdefgh";
char* s2 = "def";
char* s3 = "dee";
// 匹配成功，返回指向 'd' 的指针，打印结果为 defgh
printf("%s\n", strstr(s1, s2));
// 匹配失败，返回空指针
printf("%s\n", strstr(s1, s3));
return 0;
}BF 算法（暴力匹配）模拟实现
BF 算法即 Brute Force 算法，是最直观的字符串匹配策略。其思想是从主串的第一个字符开始，逐个与模式串字符比对。若相等则继续比较下一位；若不相等，主串指针回溯到当前起始位置的下一个字符，模式串指针重新回到首位，直到遍历结束。
实现逻辑如下：利用两层循环，外层遍历主串索引 i，内层比较字符。若内层循环完成且模式串长度全部匹配，说明找到目标；若中途不匹配，重置索引继续尝试。
#include <assert.h>
#include <string.h>
char* my_strstr(char* str1, char* str2){
assert(str1 && str2);
int slen = strlen(str1);
int sublen = strlen(str2);
int i = 0; // 主串指针
int j = 0; // 模式串指针
int count = 0; // 记录每次匹配的起始位置
while(i < slen){
// 内层循环：逐字符比较
while(str1[i] == str2[j] && j < sublen){
++i;
++j;
}
// 情况一：模式串完全匹配
if(j >= sublen){
// 返回子串在主串中的起始地址
return str1 + i - j;
}
// 情况二：匹配失败，回溯
++count;
i = count; // 主串回溯至下一次起始位
j = 0; // 模式串重置
}
return NULL;
}KMP 算法核心原理
KMP 算法是对 BF 的优化，由 D.E.Knuth、J.H.Morris 和 V.R.Pratt 提出。其核心优势在于：主串指针不需要回溯，仅在模式串内部移动。通过预先计算模式串的 next 数组，记录局部匹配信息，从而在失配时跳过已知的重复部分，大幅减少比较次数。
KMP 与 BF 的主要区别在于：当发生失配时，BF 算法会回退主串指针，而 KMP 算法保持主串指针不动，仅通过 next 数组调整模式串指针位置。
KMP 算法模拟实现 strstr
实现 KMP 需分两步：首先构建 next 数组，然后执行匹配逻辑。
- 构建 next 数组：
next[k]表示模式串前k个字符中，最长相等前后缀的长度。初始化next[0]=-1, next[1]=0，通过递推计算后续值。 - 执行匹配：
当字符匹配时，双指针同时后移；当失配时，主串i不变，模式串j跳转至next[j]。若j=-1，则双指针均后移以开始新一轮比较。
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
// 构建 next 数组
void get_next(int* next, char* sub){
int len = strlen(sub);
next[0] = -1;
if(len > 1) next[1] = 0;
int i = 2;
int k = 0;
while(i < len){
// 若 k=-1 或前缀字符等于后缀字符
if(k == -1 || sub[i-1] == sub[k]){
next[i] = ++k;
++i;
}else{
// 回溯 k 值
k = next[k];
}
}
}
char* my_strstr(char *str1, char * str2){
assert(str1 && str2);
int slen = strlen(str1);
int sublen = strlen(str2);
// 动态分配 next 数组内存
int* next = (int*)malloc(sizeof(int)*sublen);
assert(next);
get_next(next, str2);
int i = 0;
int j = 0;
// 匹配循环
while(i < slen && j < sublen){
if(j == -1 || str1[i] == str2[j]){
++i;
++j;
}else{
// 失配时，j 根据 next 数组回溯
j = next[j];
}
}
// 判断是否完全匹配
if(i >= sublen && j == sublen) {
return str1 + i - j;
} else {
free(next); // 释放内存
return NULL;
}
}以上就是C语言strstr函数模拟实现的详细内容，更多关于C语言算法优化的资料请关注本站其它相关文章！
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
