字符串处理算法：最长公共子串的算法设计与 C 代码实现

在字符串处理的领域中，最长公共子串问题是一个常见且具有重要意义的问题。它在文本比较、模式匹配、数据压缩等众多应用中发挥着关键作用。

最长公共子串指的是在两个或多个字符串中长度最大且连续相同的子串。为了有效地解决这个问题，我们需要设计一种高效的算法。

一种常见的算法是动态规划算法。其基本思想是构建一个二维数组来记录两个字符串在不同位置的匹配情况。通过逐步比较两个字符串的字符，根据匹配结果更新数组的值。

下面是用 C 语言实现最长公共子串算法的示例代码：

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

void longestCommonSubstring(char *str1, char *str2) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);

    int dp[len1 + 1][len2 + 1];
    int maxLength = 0;
    int endIndex = 0;

    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > maxLength) {
                    maxLength = dp[i][j];
                    endIndex = i - 1;
                }
            } else {
                dp[i][j] = 0;
            }
        }
    }

    if (maxLength > 0) {
        char *result = (char *)malloc((maxLength + 1) * sizeof(char));
        strncpy(result, str1 + endIndex - maxLength + 1, maxLength);
        result[maxLength] = '\0';
        printf("最长公共子串: %s\n", result);
        free(result);
    } else {
        printf("没有公共子串\n");
    }
}

int main() {
    char str1[] = "ABCDGH";
    char str2[] = "AEDFHR";

    longestCommonSubstring(str1, str2);

    return 0;
}

在上述代码中，我们首先定义了一个二维数组 dp 来保存中间计算结果。通过两个嵌套的循环遍历两个字符串，根据字符匹配情况更新数组的值。最终找到最长公共子串并输出。

最长公共子串算法的设计和实现对于提高字符串处理的效率和准确性具有重要意义。熟练掌握这一算法，能够在实际的编程任务中更加高效地处理字符串相关的问题。