题解 | #查找两个字符串a,b中的最长公共子串#
查找两个字符串a,b中的最长公共子串
http://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main()
{
char str1[308], str2[308], temp[308];
scanf("%s%s", str1, str2);
int len1 = strlen(str1), len2 = strlen(str2), i, j, commonlen = 0, index = -1, t, flag = 0;
if(len2 < len1){
strcpy(temp, str1);
strcpy(str1, str2);
strcpy(str2, temp);
t = len1;
len1 = len2;
len2 = t;
}
int dp[len1][len2];
memset(dp, 0, sizeof(int) * len1 * len2);
for(i = 0; i < len1; i++){
if(str1[i] == str2[0]){
dp[i][0] = 1;
if(dp[i][0] > commonlen){
commonlen = 1;
index = i;
}
}
}
for(i = 0; i < len2; i++){
if(str2[i] == str1[0]){
dp[0][i] = 1;
if(commonlen == 0){
commonlen = 1;
flag = 1;
}
}
}
for(i = 1; i < len1; i++){
for(j = 1; j < len2; j++){
if(str1[i] == str2[j]){
dp[i][j] = dp[i-1][j-1] + 1;
if(dp[i][j] > commonlen){
commonlen = dp[i][j];
index = i;
}
}
}
}
if(flag == 1 && commonlen == 1){
printf("%c", str1[0]);
}
else{
if (index >= 0){
for(i = index - commonlen + 1; i <= index; i++){
printf("%c", str1[i]);
}
}
}
printf("\n");
return 0;
}
