C语言两个字符串的最长子串的代码

在C语言中，可以使用动态内存分配和KMP算法（Knuth-Morris-Pratt算法）来找到两个字符串之间的最长公共子串。下面是一个简单的KMP算法实现示例：

#include <stdio.h>
#include <string.h>

// 定义辅助函数用于构建部分匹配表
void getPartialMatchTable(char *pattern, int len, int* lps) {
    int index = 0;
    lps[0] = 0;
    for (int i = 1; i < len; ++i) {
        if (pattern[i] == pattern[index]) {
            index++;
            lps[i] = index;
        } else {
            if (index != 0)
                index = lps[index - 1];
            else
                lps[i] = 0;
        }
    }
}

// KMP搜索最长公共子串
char* longestCommonSubstring(char* str1, char* str2) {
    int m = strlen(str1);
    int n = strlen(str2);
    int* lps = (int*)malloc(sizeof(int) * n);
    getPartialMatchTable(str2, n, lps);

    int maxLen = 0, end = 0;
    char* result = NULL;

    for (int i = 0; i < m; ++i) {
        while (end > 0 && str1[i] != str2[end]) {
            end = lps[end - 1];
        }

        if (str1[i] == str2[end]) {
            end++;
        }

        if (i + 1 - end > maxLen) {
            maxLen = i + 1 - end;
            result = (char*)malloc((maxLen + 1) * sizeof(char));
            strncpy(result, &str1[i - maxLen], maxLen + 1);
            result[maxLen] = '\0';
        }
    }

    free(lps);
    return result;
}

int main() {
    char str1[] = "ABABC";
    char str2[] = "BABCA";
    char* lcs = longestCommonSubstring(str1, str2);
    printf("Longest common substring: %s\n", lcs);
    free(lcs);
    return 0;
}

这个代码首先计算了`str2`的最长公共前缀数组（lps），然后遍历`str1`，利用lps数组找到每个位置最长公共子串的结束位置。最后找到最长公共子串并返回。