描述：

计算两个字符串的最大公共子串（Longest Common Substring）的长度，字符不区分大小写。

输入：

输入两个字符串

输出：

输出一个整数

样例输入：

asdfas werasdfaswer

样例输出：

6

这里的最大公共字串要求的字串是连续的。

求字串的方法和求子序列方法类似：

当str1[i] == str2[j]时，子序列长度veca[i][j] = veca[i - 1][j - 1] + 1；只是当str1[i] ！= str2[j]时，veca[i][j]长度要为0，而不是max{veca[i - 1][j], veca[i][j - 1]}。

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 void LongestSubstr(string &s1, string &s2) 7 { 8     int len1 = s1.size(), len2 = s2.size(); 9     vector
         
          
           > c(len1+1, vector
           
            (len2+1,0));10 for (int i = 0; i <= len1; i++)11 c[i][0] = 0;12 for (int j = 0; j <=len2; j++)13 c[0][j] = 0;14 int max = 0,x=0,y=0;15 for(int i=1;i<=len1;i++)16 for (int j = 1; j <=len2; j++)17 {18 if (s1[i-1] == s2[j-1])19 {20 c[i][j] = 1 + c[i - 1][j - 1];21 }22 else 23 {24 c[i][j] = 0;25 }26 //记录最长子串最后一个位置27 if (c[i][j] > max)28 {29 max = c[i][j];30 x = i;31 y = j;32 }33 }34 int a = x - 1, b = y - 1;35 string s;36 while (a >= 0 && b >= 0)37 {38 if (s1[a] == s2[b])39 {40 s += s1[a];41 a--;42 b--;43 }44 else break;45 }46 reverse(s.begin(),s.end());47 cout << s;48 }49 50 int main()51 {52 string s1 = "ABCBDAB";53 string s2 = "BDCABA";54 LongestSubstr(s1,s2);55 56 }