最大公共子串长度问题就是:
求两个串的所有子串中能够匹配上的最大长度是多少。
比如:“abcdkk” 和 “baabcdadabc”,
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
最大公共子串长度问题就是:
求两个串的所有子串中能够匹配上的最大长度是多少。
比如:“abcdkk” 和 “baabcdadabc”,
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
供参考:
#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;
}