关于题目理解，请注意和最长公共子序列的区别，最长公共子字符串的解法是动态规划，但是比较难想到表的构造方法。
注意到，设给定字符串为str1 和 str2 ,二者的长度分别是 len1 和 len2 ,那么解空间大小之多是len1*len2？（假设最长公共子字符串为substr_common，那么substr_common在str1 中的结束位置或者起始位置只有len1种选择，而在str2中则最多len2种选择，故解空间最大为len1*len2)。对于解空间中的每一个解都对应着自己的长度，网站空间，因为一旦结束位置都确定，即意味着公共子字符串找到了。
如果用蛮力法做的话，遍历解空间需要时间复杂度为O(len1*len2)，然后确定每个解的长度需要的时间是O(min(len1,len2))，所以基本上是个O(n3)的算法，显然不妥。
前面说过，这道题可以用动态规划来做，动态规划最关键的是找到最优子结构，一般来说，最优子结构意味着问题可以找到一种递归的，美国空间，不断缩小问题规模的解决方式，与分治法不同，动态规划的小问题之间有重叠，但是这个问题好像不是那么好找到一种递归的表达形式。
要缩小问题规模，一种最简单的想法肯定是缩小str1规模，或者缩小str2规模，或者二者同时缩小，而缩小的方式肯定是增减元素了，能用动态规划做必定有个自底向上的过程，很少有直接二分的， 直接二分是分治法的策略，所以增减一般在头尾增减，以此题为例，为保持一致性，在分析题目的过程设两个字符串都由尾部向头减少，而在解决问题的过程中是由头部向尾部增加。我们可以构建一张表count[len1][len2] , 其中count[i][j] 表示如果公共子字符串在str1的第i个位置结束，在str2的第j个位置结束时公共子字符串的长度。从底向上开始构建这张表，下面是增减的描述：假设目前需要计算count[i][j]，有以下几种情况：
1. str1[i] == str2[j] : 此时count[i][j] = count[i-1][j-1]+1
2. str1[i] != str2[j] : 很显然，服务器空间，以i,j为结束点的解 count[i][j] = 0 .
因此，一旦知晓了count[i-1][0,….,len2] ,count[i][0,….,len2]可以顺序获得，以str1 = “1234”, str2 = “2345”为例，表的构造方式如下：
只要在构建表的过程中记住当前最长的子字符串长度和结束位置，就可以很轻易地打印出最长公共子字符串，与之相对应的代码如下：
/* author : lipan date : 2013.07.29 email : areslipan@163.com*/#include <stdio.h>#include <stdlib.h>int lcs_substring(char *str1,char *str2,int str1_len,int str2_len);int main(){ int str1_len = 0; int str2_len = 0; printf(“Please input the length of two sequence : “); scanf(“%d%d”,&str1_len,&str2_len); char *str1 = (char *)malloc((str1_len)*sizeof(char)); char *str2 = (char *)malloc((str2_len)*sizeof(char)); printf(“Please input the two sequence:\n”); scanf(“%s%s”,str1,str2); lcs_substring(str1,str2,str1_len,str2_len); return 0;}int lcs_substring(char *str1,char *str2,int str1_len,int str2_len){ //动态规划表 char *record = (char *)malloc(str2_len*str1_len*sizeof(char)); //分别记录当前最长的子字符串长度，截止位置 int maxSubStrLen = 0; int maxSubStrH = 0; int maxSubStrW =0; for(int h =0;h<str1_len;h++) {for(int w=0;w<str2_len;w++){if(str1[h]==str2[w]){if(h == 0||w == 0){record[h*str1_len+w]=1; }else{record[h*str1_len+w] = record[(h-1)*str1_len+w-1]+1;}if(maxSubStrLen<record[h*str1_len+w]){maxSubStrLen = record[h*str1_len+w];maxSubStrW= w;maxSubStrH= h;}}} } //输出最长公共子字符串 printf(“the longest common substring is :”); for(int i = maxSubStrW-maxSubStrLen+1;i<=maxSubStrW;i++) {printf(“%c”,str2[i] ); } return maxSubStrLen;}婚姻犹如一艘雕刻的船，看你怎样去欣赏它，又怎样驾驭它。
