姊妹篇：最长公共子串

上一次讲解了最长公共子序列，这次·来求解下最长公共子串

先回顾下最长公共子序列问题，因为子序列没必要连续，所以当子串A中的第x个元素与子串B中的第y个元素不等时，可以先掩掉一个元素，然后剩下的子串再与另外一个子串相比，最终得出最优解。

但是最长公共子串问题呢，一字之差，它的思想又发生了变化，这样变化理解起来是困难的，

刚开始给我一种感觉，子串A中的第x个元素与子串B中的第y个元素不等时，不能再像最长公共子序列那样掩去其中一个元素去探测，而是应该从0开始，为什么？因为它已经断掉了
举例来说吧

A : ABCDEF
B：ABDDEF

若求最长公共子序列，显示是5，但是求公共子串，只能是3，下面说一下大致的思路吧，若str1[i]==str2[j]，则dp[i][j]=dp[i-1][j-1]+1，否则为0，这就是递推公式

#include <iostream>
using namespace std;
int main(){string str1 = "CDEABE";string str2 = "ABCDE";int ** dp = new int*[str1.length()+1];for(int i=0;i<=str1.length();i++){dp[i] = new int[str2.length()+1];}for(int i=0;i<=str1.length();i++)for(int j=0;j<=str2.length();j++)dp[i][j]=0;for(int i=1;i<=str1.length();i++){for(int j=1;j<=str2.length();j++){if(str1[i-1]!=str2[j-1]){dp[i][j] = 0;}else{dp[i][j] = dp[i-1][j-1]+1;}}}int max = 0;for(int i=0;i<=str1.length();i++){for(int j=0;j<=str2.length();j++)if(dp[i][j] > max) max = dp[i][j];}cout<<max<<endl;return 0;
}