用C++编程求两个字符串的最长公共子串

来源:百度知道 编辑:UC知道 时间:2024/06/16 02:22:17
要求:输入两个字符串,输出它们的最长公共子串,包括长度.
那位大虾,知道的帮下谢谢

很复杂的

int MaxSubString(const char *str1,const char *str2,char * &s) {
int i, j, k, index, max=0;
for(i=0; str1[i]; i++)
for(j=0; str2[j]; j++) {
for(k=0; str1[i+k]==str2[j+k] && (str2[i+k] || str1[i+k]); k++);
if(k>max) { // 出现大于当前子串长度的子串,则替换子串位置和程度
index = j; max = k;
}
}
s = (char *)calloc(sizeof(char), max+1);
for(i=0; i<max; i++)
s[i] = str2[index++];
return max;
}

int main(int argc, char* argv[]) {
char str1[] = "abractyeyt", str2[] = "dgdsaeactyey";
char *s;
int length = MaxSubString(str1, str2,s);
printf("str1=%s\nstr2=%s\nMaxSubString=%s ,length=%d\n", str1, str2, s,length);
}