用C语言解决一个最大公共子串长度问题

Question

最大公共子串长度问题就是：

求两个串的所有子串中能够匹配上的最大长度是多少。

比如：“abcdkk” 和 “baabcdadabc”，

可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。

Answer 1

供参考：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int  getCommon(char str1[], char str2[], char* str3);
int  main() {
    char str1[50], str2[50], str3[50];
    int  max = 0;
    gets(str1);
    gets(str2);
    max = getCommon(str1, str2, str3);
    printf(max == 0 ? "max=%d\n" : "max=%d, %s\n", max, str3);
    return 0;
}
int getCommon(char str1[], char str2[], char* str3) {
    int len1, len2;
    int i, j, k;
    int max = 0;
    int start = -1;
    len1 = strlen(str1);
    len2 = strlen(str2);
    for (i = 0; i < len1; i++) {
        for (j = 0; j < len2; j++) {
            if (str1[i] == str2[j]) {
                for (k = 0; (str1[i + k] == str2[j + k] && str1[i + k] != '\0'); k++);
                if (max < k) {
                    max = k;
                    start = i;
                }
            }
        }
    }
    if (start == -1) {
        str3[0] = '\0';
    }
    else {
        memcpy(str3, &str1[start], max);
        str3[max] = '\0';
    }
    return max;
}