这是一个很基础的问题，给定两个字符串，查找两个字符串中最长得公共子串，例如给定串S1="abcdefg" S2="bcdeefg"，则其中最长得公共子串便是bcde。
补充： 今天回过来看这个问题，发现解答的还是存在很多问题，把题目做复杂了。更加简单的解法可以参考这个链接：http://blog.csdn.net/steven30832/article/details/8260189 我又重新按照上面的思路实现了多种解法，具体可以参考我的代码，点这儿。
看到这个问题，依然是动态规划求解，当然可能还有其他的思路，例如使用编程珠玑中提到求解字符串中最长重复子串的问题。随便提下后缀数组，可以在O(OlogN)的情况下查找出最长重复子串，若直接将后缀数组使用到这个题目里面来，需要将两个字符串连接起来，然后再转换成最长重复子串的问题，为了避免无法分清两个字符串的边界，则需要添加一个标识符，例如，S1="abcdabcd" S2="abc",对于这两个字符串，使用一个‘#’连接，变成abcdabcd#abc,然后在排序比较之时，确保前后两个地址是属于不同的字符串。
依然使用动态规划来分析此问题，需要递归表达式，边界条件和中间过程。其中F(i,j)表示从后往前比较，字符串S1的前i个字符和字符串S2的前j个字符中最长得公共子串，由三部分确定，
F(i,j) = max{max{F(i-k,j-k),k},F(i-1,j),F(i,j-1)} (0 <= i < strlen(s1), 0 <= j < strlen(s2))
中间过程便是记录不同F(i,j)值，边界条件则是若i或者j为0，则公共子串长度为0了。
根据上面的分析可以很迅速的写出下面的代码。
int findCommonSequence(const char* first, int flen, const char* second, int slen,int **state){
if(flen <= 0 || slen <= 0)
return 0;
int one = 0, two = 0,three = 0;
if(state[flen][slen] >= 0)
return state[flen][slen];
if(first[flen-1] == second[slen-1]){
int i = flen - 1,j = slen -1;
while(i >= 0 && j >= 0 && first[i--] == second[j--]){
one++;
}
int next = findCommonSequence(first,flen-one,second,slen-one,state);
state[flen-one][slen-one] = next;
one = max(one,next);
}
two = findCommonSequence(first,flen-1,second,slen,state);
state[flen-1][slen] = two;
three = findCommonSequence(first,flen,second,slen-1,state);
state[flen][slen-1] = three;
state[flen][slen] = max(one,two,three);
return state[flen][slen];
}
可以使用回溯来确定起点何在
int backtracing(int **state,int flen, int slen){
if(state == NULL)
return -1;
while(flen >= 0){
if(state[flen][slen] == state[flen-1][slen]){
flen--;
}else if(state[flen][slen] == state[flen-1][slen] + 1){
return flen - state[flen][slen];
}
}
}
类似与这样的问题也有很多，除了前面提到的最长重复子串之外，还有一些。 * 两个字符串的编辑距离 * 最长的回文子串 * 字符串匹配KMP算法
其中编辑距离和这个没什么区别，后面两个思路大致相同，都是进行遍历比较，只是在遍历过程中，使用技巧，减少重复得遍历比较，KMP算法，则需要一个next数组，记录比较失败之后，下次可以从哪儿开始接着比较，这样就不要回到起点重新比较，回文子串，则是利用回文串本身的特点对称性,然后将两种不同对称归一化，奇数对称和偶数对称都转换成奇数对称，找到一个回文串之后，由于对称，下次就可以减少其中的比较。