问题描述：

    给定两个序列 X=<x1, x2, ..., xm>, Y<y1, y2, ..., yn>，求X和Y长度最长的公共子串。(子串中的字符要求连续)

 

    这道题和很像，也可以用动态规划定义。公式如下：

这里c[i,j]表示以Xi,Yj结尾的最长公共子串的长度。

程序实现：

int longestCommonSubstring(string x, string y){    int m = x.length();    int n = y.length();    vector< vector
     
       > c(m+1, vector
      
       (n+1));    for (int i = 0; i <= m; ++i)        c[i][0] = 0;    for (int j = 1; j <= n; ++j)        c[0][j] = 0;    int len = 0;    for (int i = 1; i <= m; ++i)    {        for (int j = 1; j <= n; ++j)        {            if (x[i-1] == y[j-1])            {                c[i][j] = c[i-1][j-1] + 1;                if (c[i][j] > len)                    len = c[i][j];            else                c[i][j] = 0;        }    }    return len;}
      
     

reference：