C语言求解最长公共子字符串问题及相关的算法分析

简介

在文本处理中，求解最长公共子字符串问题是一个普遍的、重要的问题。该问题描述如下：给定两个字符串s1和s2，求它们的最长公共子字符串，即在两个字符串中都出现过的最长的子串。

算法分析

在求解最长公共子字符串问题中，有多种不同的算法，这里介绍两种常用的算法：暴力枚举和动态规划。

暴力枚举算法

暴力枚举算法是最朴素、最简单的算法，也是一种较慢的算法。该算法基本思路是：枚举s1的所有子串和s2的所有子串，判断它们是否相等，记录最长的相等子串即可。

暴力枚举算法的时间复杂度为O(n^3)，但它实现简单易懂，可以作为其他算法的比较标准。下面给出暴力算法的C语言实现代码：

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

int max(int a, int b)
{
    return a > b ? a : b;
}

int getLCS(char* s1, char* s2, int len1, int len2)
{
    int maxLCS = 0;
    int len;
    for (int i = 0; i < len1; i++)
    {
        for (int j = 0; j < len2; j++)
        {
            len = 0;
            while (i + len < len1 && j + len < len2 && s1[i+len] == s2[j+len])
            {
                len++;
            }
            maxLCS = max(maxLCS, len);
        }
    }
    return maxLCS;
}

int main()
{
    char s1[] = "abcde";
    char s2[] = "bdewfabc";
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int res = getLCS(s1, s2, len1, len2);
    printf("The length of the LCS is %d\n", res);
    return 0;
}

动态规划算法

动态规划算法是一种常用的、高效的算法，它的基本思路是将原问题分解成多个子问题，通过保存中间结果，避免重复计算，实现高效求解。该算法在求解最长公共子字符串问题时，需要构建一个二维的DP矩阵，通过矩阵的更新计算出最长公共子串的长度。

动态规划算法的时间复杂度为O(n^2)，要比暴力算法的时间复杂度低得多，下面给出动态规划算法的C语言实现代码：

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

int max(int a, int b)
{
    return a > b ? a : b;
}

int getLCS(char* s1, char* s2, int len1, int len2)
{
    int maxLCS = 0;
    int dp[len1+1][len2+1];
    for (int i = 0; i <= len1; i++)
    {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= len2; j++)
    {
        dp[0][j] = 0;
    }
    for (int i = 1; i <= len1; i++)
    {
        for (int j = 1; j <= len2; j++)
        {
            if (s1[i-1] == s2[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
                maxLCS = max(maxLCS, dp[i][j]);
            }
            else
            {
                dp[i][j] = 0;
            }
        }
    }
    return maxLCS;
}

int main()
{
    char s1[] = "abcde";
    char s2[] = "bdewfabc";
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int res = getLCS(s1, s2, len1, len2);
    printf("The length of the LCS is %d\n", res);
    return 0;
}

上述代码中使用了一个二维的DP矩阵，通过分别比较s1的第i个字符和s2的第j个字符，判断是否相等，来更新矩阵中dp[i][j]的值。最终DP矩阵中的最大值即为最长公共子串的长度。

示例说明

下面给出两个示例说明，分别使用暴力枚举算法和动态规划算法，求解两个字符串的最长公共子串长度。

示例1：使用暴力枚举算法求解

s1 = "ABCBAB", s2 = "BABCBABC"

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

int max(int a, int b)
{
    return a > b ? a : b;
}

int getLCS(char* s1, char* s2, int len1, int len2)
{
    int maxLCS = 0;
    int len;
    for (int i = 0; i < len1; i++)
    {
        for (int j = 0; j < len2; j++)
        {
            len = 0;
            while (i + len < len1 && j + len < len2 && s1[i+len] == s2[j+len])
            {
                len++;
            }
            maxLCS = max(maxLCS, len);
        }
    }
    return maxLCS;
}

int main()
{
    char s1[] = "ABCBAB";
    char s2[] = "BABCBABC";
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int res = getLCS(s1, s2, len1, len2);
    printf("The length of the LCS is %d\n", res);
    return 0;
}

输出结果为：The length of the LCS is 3

示例2：使用动态规划算法求解

s1 = "ABCBAB", s2 = "BABCBABC"

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

int max(int a, int b)
{
    return a > b ? a : b;
}

int getLCS(char* s1, char* s2, int len1, int len2)
{
    int maxLCS = 0;
    int dp[len1+1][len2+1];
    for (int i = 0; i <= len1; i++)
    {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= len2; j++)
    {
        dp[0][j] = 0;
    }
    for (int i = 1; i <= len1; i++)
    {
        for (int j = 1; j <= len2; j++)
        {
            if (s1[i-1] == s2[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
                maxLCS = max(maxLCS, dp[i][j]);
            }
            else
            {
                dp[i][j] = 0;
            }
        }
    }
    return maxLCS;
}

int main()
{
    char s1[] = "ABCBAB";
    char s2[] = "BABCBABC";
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int res = getLCS(s1, s2, len1, len2);
    printf("The length of the LCS is %d\n", res);
    return 0;
}

输出结果为：The length of the LCS is 3

以上两个示例分别展示了使用暴力枚举算法和动态规划算法求解最长公共子字符串问题的基本思路和操作过程。