C语言实现strstr功能：自定义函数查找子串及优化解析

C语言查找子串的基本逻辑

在C语言的面试或基础算法练习中，通常要求不依赖中的标准函数（如strstr），而是手动实现一个函数：char * search(char * s, char * t)。该函数的目标是在源字符串 s 中查找目标子串 t 的首次出现位置，若找到则返回指向该位置的指针，否则返回 NULL。

第1步：动态输入的处理与内存分配

为了处理长度未知的字符串，使用 malloc 和 realloc 进行动态内存分配是最灵活的方式。这样可以避免固定数组可能导致的缓冲区溢出。

// 读取主串 s
char *s = (char *)malloc(sizeof(char));
int count = 0;
char ch;
while((ch = getchar()) != '\n') {
    s[count] = ch;
    count++;
    s = (char *)realloc(s, (count + 1) * sizeof(char)); // 动态扩容
}
s[count] = '\0';

注意：在循环中调用 realloc 虽然方便，但在高频场景下性能不如预先分配较大空间（如每次增加10个字节）来得高效。对于常规练习，上述写法足以满足需求，且务必在程序结束前释放内存。

第2步：核心查找算法（暴力匹配）

最直观的方法是双重循环：外层遍历主串 s 的每个可能的起始位置，内层从子串 t 的第一个字符开始逐个比对。如果内层循环全部匹配成功，则说明找到了子串。

char* search(char *s, char *t) {
    int size_t = strlen(t);
    int size_s = strlen(s);
    // 如果子串比主串长，直接返回NULL
    if (size_t > size_s) return NULL;
    
    char *p = NULL;
    // 遍历主串的有效起始范围
    for (int i = 0; i <= (size_s - size_t); i++) {
        p = s + i; // 指向当前可能的起始点
        int match = 1; // 标记是否匹配
        for (int j = 0; j < size_t; j++) {
            if (*p != *(t + j)) { // 字符不一致
                match = 0;
                break;
            }
            p++; // 同时移动两个指针
        }
        if (match == 1) {
            // 找到匹配项，恢复指针位置或直接计算地址
            // 由于上面p已经后移了，需要返回s+i
            return s + i;
        }
    }
    return NULL;
}

上述代码展示了经典的 KMP 之前缀暴力匹配逻辑。如果存在完全匹配的子串，函数将返回 s+i，即子串首字符的地址。

在程序运行测试时，可以通过如下方式观察结果：

OJ实战：浙江大学PTA题目解析

除了手写完整的输入输出流程，在很多在线判题系统（如浙江大学PTA）中，通常只提供核心函数的接口定义，由裁判系统负责读取输入和打印结果。这考察的是更纯粹的算法逻辑。

题目要求

• 函数原型：char *search( char *s, char *t );
• 返回值：若未找到，返回 NULL；若找到，返回子串在 s 中的首地址。
• 主逻辑：裁判程序会计算 pos - s 来得到从0开始的偏移量索引。

方法一：基于下标的实现（更易理解）

不使用指针运算，而是利用数组下标和计数器来判断。这种方式对初学者更友好，避免了复杂的指针回溯问题。

char *search(char *s, char *t) {
    int n1 = 0, n2 = 0, m = 0;
    int i, j;
    
    // 获取子串长度 n1
    while(t[n1]) n1++;
    // 获取主串长度 n2
    while(s[n2]) n2++;
    
    // 边界检查
    if(n1 == 0) return s; // 空串直接返回
    if(n1 > n2) return NULL; // 子串更长，不可能匹配

    for(i = 0; i <= n2 - n1; i++) {
        m = 0; // 重置匹配计数
        for(j = 0; j < n1; j++) {
            if(s[i+j] == t[j]) {
                m++; // 字符相同，计数加1
            } else {
                break; // 不同则中断当前轮次的匹配
            }
        }
        // 如果本轮所有字符都匹配成功了
        if(m == n1) {
            return &s[i]; // 返回子串起始位置的指针
        }
    }
    return NULL; // 未找到
}

方法二：基于指针的移动

利用指针直接指向字符，通过 *s 判断结束标志 '\0'，适合深入理解内存布局。

char *search(char *s, char *t) {
    // 简单思路：逐位比较
    while(*s) {
        char *p = s, *q = t;
        while(*q && (*p == *q)) {
            p++; q++;
        }
        if(*q == '\0') {
            return s; // 找到了，q回到了\0，说明完全匹配
        }
        s++;
    }
    return NULL;
}

总结

在C语言中查找子串不仅仅是调用 strstr 那么简单。掌握底层的手动匹配过程，有助于处理内存安全、指针越界等问题。在实际工程中，如果是非性能瓶颈的代码，直接使用标准库函数；如果是学习或特定的嵌入式环境，则需要依据上述逻辑实现高效的匹配算法。以上就是C语言查找子串问题的详细内容，更多关于C语言字符串处理与指针应用的资料请关注本站其它相关文章！