定义dp[i][j]表示字符串str1中第i个字符和str2种第j个字符为最后一个元素所构成的最长公共子串。如果要求dp[i][j],也就是str1的第i个字符和str2的第j个字符为最后一个元素所构成的最长公共子串,我们首先需要判断这两个字符是否相等。
如果不相等,那么他们就不能构成公共子串,也就是
dp[i][j]=0;
如果相等,我们还需要计算前面相等字符的个数,其实就是dp[i-1][j-1],所以
dp[i][j]=dp[i-1][j-1]+1;
有了递推公式,代码就比较简单了,我们使用两个变量,一个记录最长的公共子串,一个记录最长公共子串的结束位置,最后再对字符串进行截取即可,来看下代码
/*** longest common substring* @param str1 string字符串 the string* @param str2 string字符串 the string* @return string字符串*/char* LCS(char* str1, char* str2 ) {// write code hereint str1Len = strlen(str1);int str2Len = strlen(str2);int dp[5000][5000] = {{0}};int i,j;int maxLen = 0;int maxIndex = 0;for(i=1; i<=str1Len; i++){for(j=1; j<=str2Len; j++){if(str1[i-1] == str2[j-1]){dp[i][j] = dp[i-1][j-1] +1;if(maxLen < dp[i][j]){maxLen = dp[i][j];maxIndex = i;}}else{dp[i][j] = 0;}}}str1[maxIndex] = '\0';return str1+maxIndex-maxLen;}
动态规划代码优化
上面我们使用的是二维数组,我们发现计算当前位置的时候之和左上角的值有关,所以我们可以把二维数组变为一维数组,注意第2个for循环要进行倒叙,因为后面的值要依赖前面的值,如果不倒叙,前面的值会被覆盖,导致结果错误
/*** longest common substring* @param str1 string字符串 the string* @param str2 string字符串 the string* @return string字符串*/char* LCS(char* str1, char* str2 ) {// write code hereint str1Len = strlen(str1);int str2Len = strlen(str2);int *dp= (int *)malloc((str2Len+1)*sizeof(int));memset(dp,0,str2Len);int i,j;int maxLen = 0;int maxIndex = 0;for(i=1; i<=str1Len; i++){for(j=str2Len; j>=1; j--){if(str1[i-1] == str2[j-1]){dp[j] = dp[j-1] +1;if(maxLen < dp[j]){maxLen = dp[j];maxIndex = i;}}else{dp[j] = 0;}}}str1[maxIndex] = '\0';free(dp);return str1+maxIndex-maxLen;}