C语言实现求两个字符串的最长公共子串

算法原理与目标

最长公共子串（Longest Common Substring）要求两个字符串中存在的一段连续的字符序列完全相同。与最长公共子序列不同，子串必须是连续的。本示例的目标是输入两个字符串，输出其中最长的那一段公共部分。

准备条件与环境

你需要一个支持标准C语言的编译器或开发环境。代码仅依赖标准库 stdio.h、string.h 和 stdlib.h，无需额外安装第三方库。由于涉及内存拷贝，需确保目标缓冲区足够大以容纳结果。

具体实现步骤

第1步：构建自定义字符串长度函数

目的：虽然标准库提供了 strlen，但示例代码展示了手动计算字符串长度的逻辑，有助于理解底层机制。

操作：定义一个遍历字符直到遇到结束符 '\0' 的指针函数。

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

int stringLength(char * str){
    int len = 0;
    while(*str != '\0'){
        len++;
        str++;
    }
    return len;
}

第2步：实现最长公共子串核心逻辑

目的：通过三层嵌套循环找出最大匹配长度及其在第一个字符串中的起始位置。

参数说明： - str1[], str2[]：待比较的两个源字符串。 - *str3：用于存储结果的目标缓冲区。

动作： 1. 使用变量 max 记录当前发现的最大长度，start 记录对应的起始索引（初始为 -1 表示未找到）。 2. 外层两重循环遍历 str1 和 str2 的每个字符组合。

void getCommon(char str1[],char str2[],char * str3){
    int len1,len2;
    int i,j,k;
    int max=0;
    int start = -1;

    len1 = stringLength(str1);
    len2 = stringLength(str2);
    
    for(i = 0; i < len1; i++){
        for(j = 0; j < len2; j++){
            if(str1[i] == str2[j]){
                // 向后查找连续匹配的长度
                for(k = 0; (str1[i+k] == str2[j+k] && str1[i+k] != '\0'); k++);
                if(max < k){
                    max = k;
                    start = i;
                }
            }
        }
    }
    // ... 后续截取逻辑见下文

第3步：结果截取与安全处理

目的：将计算出的最大子串复制到结果缓冲区，并正确终止字符串。

重要参数：确保 str3 有足够的空间（至少 max + 1 字节）。

动作： - 如果 start == -1，说明无公共子串，将结果设为空字符串。 - 否则，使用 memcpy 从 str1 的起始位置复制 max 个字节，并在末尾添加 '\0'。

if(start == -1){
    str3[0] = '\0';
}else{
    memcpy(str3,&str1[start],max);
    str3[max] = '\0';
}

第4步：主函数调用与测试

入口：程序启动入口 main。

操作： 1. 定义长度为50的字符数组存储输入和输出。 2. 使用 gets 读取用户输入的字符串（注意：gets 不安全，生产环境建议用 fgets）。 3. 调用 getCommon 并打印结果。

void main(){
    char str1[50];
    char str2[50];
    char str3[50];
    gets(str1);
    gets(str2);
    getCommon(str1,str2,str3);
    printf("%s\n",str3);
}

完成判断与排错

成功标志：编译无错误，运行时输入两个包含公共部分的字符串（如 "abcde" 和 "bcdef"），输出预期结果 "bcde"。
常见问题： 1. **缓冲区溢出**：若字符串超过50字符，需增大数组定义。
2. gets 安全警告：现代编译器可能禁用 gets，如需严格符合标准，请替换为 fgets(str, sizeof(str), stdin) 并处理尾部的换行符。

简要总结

上述方法通过暴力枚举比对实现了最长公共子串的计算，虽然时间复杂度较高（O(N^3)），但对于短字符串教学和理解算法原理非常直观。对于更长数据，通常推荐动态规划优化方案。以上就是C语言求两个字符串的最长公共子串的详细内容，更多关于C语言字符串算法的资料请关注本站其它相关文章！