Longest Common Substring

来源：nineChapter

原帖：nineChapter; dp

题目：
state: f[i][j]表示前i个字符配上前j个字符的LCS‘的长度 (一定以第i个和第j个结尾的LCS’)
function: f[i][j]  = f[i-1][j-1] + 1 // a[i] == b[j]
                  = 0 // a[i] != b[j]
intialize: f[i][0] = 0
            f[0][j] = 0
answer: MAX(f[0..a.length()][0..b.length()]

代码：

 int longestCommonSubstring(string s1, string s2) {  
   int M = s1.size(), N = s2.size();   
   vector<vector<int> > dp(M, vector<int>(N,0));  
   for (int i = 0; i <= M; ++i)  
     dp[i][0] = 0;  
   for (int j = 0; j <= N; ++j)  
     dp[0][j] = 0;  
   int maximum = 0;  
   for (int i = 1; i <= M; ++i) {  
     for (int j = 1; j <= N; ++j) {  
       if (s1[i - 1] == s2[j - 1]) {  
         dp[i][j] = dp[i - 1][j - 1] + 1;  
       } else {  
         dp[i][j] = 0;  
       }  
       maximum = max(maximum, dp[i][j]);  
     }  
   }  
   return maximum;  
 }