题解 | #公共子串计算#

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

int main() {
    
    char s1[160] = {0};
    char s2[160] = {0};
    gets(s1);
    gets(s2);

    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int dp[len1][len2];
    memset(dp, 0, sizeof(int)*len1*len2);
    int max = 0;
    int p1 = 0;
    int p2 = 0;
    for(; p2 < len2; ++ p2)
    {
        if(s1[0] == s2[p2])
        {
            dp[0][p2] = 1;
            max = max > dp[0][p2] ? max : dp[0][p2];
        }
    }
    for(; p1 < len1; ++ p1)
    {
        if(s1[p1] == s2[0])
        {
            dp[p1][0] = 1;
            max = max > dp[p1][0] ? max : dp[p1][0];
        }
    }

    for(p1 = 1; p1 < len1; ++ p1)
    {
        for(p2 = 1; p2 < len2; ++ p2)
        {
            if(s1[p1] == s2[p2])
            {
                dp[p1][p2] = dp[p1-1][p2-1] + 1;
                max = max > dp[p1][p2] ? max : dp[p1][p2];
            }
        }
    }

    printf("%d", max);

    return 0;
}