题解 | #最长公共子串#

相等且是首字母的时候最长子串为1，其他情况为+1

/**
 * longest common substring
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @return string字符串
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
char* LCS(char* str1, char* str2) {
	int l1 = strlen(str1);
	int l2 = strlen(str2);
	if (l1 == 0 || l2 == 0) {
		return NULL;
	}
	int len = 0;
	int end = 0;
	/*int** dp = (int**)malloc(sizeof(int) * l1);
	for (int i = 0; i < l1; i++) {
		dp[i] = (int*)malloc(sizeof(int) * l2);
	}*/
	int(*dp)[l2] = (int(*)[l2])malloc(sizeof(int) * l1 * l2);
	for (int i = 0; i < l1; i++) {
		for (int j = 0; j < l2; j++) {
			if (str1[i] == str2[j]) {
				if (i > 0 && j > 0) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
				else {
					dp[i][j] = 1;
				}
				if (dp[i][j] > len) {
					len = dp[i][j];
					end = i;
				}
			}
			else {
				dp[i][j] = 0;
			}
		}
	}
	str1[end + 1] = '\0';
	return str1 + end - len + 1;
}