题解 | #公共子串计算#

重点说明：采用动态规划的方法可以降低时间复杂度。本题与“最大公共子序列问题LCS”有一点不同，公共子串必须是连续的。 递推公式如下： 当s1[i-1] = s2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1; 当s1[i-1] != s2[j-1]时，dp[i][j] = 0; 式中，i=1,2..,len1 j=1,2,..len2 记录dp[i][j]中最大的值，就是公共子串的长度。

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

#define MAX(a,b) (a>b?a:b)

int get_len(int s1_start, int s2_start);

char s1[150] = {0};
char s2[150] = {0};
int dp[151][151] = {0};

int main() {
    int max_len, count;
    int len1, len2;

    while (scanf("%s %s", s1, s2) != EOF) {
        max_len = 0;
        for (int i = 1; i <= strlen(s1); i++) {
            for (int j = 1; j <= strlen(s2); j++) {
                if(s1[i-1] == s2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else{
                    dp[i][j] = 0;
                }
                
                max_len = MAX(max_len,dp[i][j]);
            }
        }
        
        printf("%d\n",max_len);
    }

    return 0;
}