1         /// 
 2         /// 动态规划：求最大公共子串 3         /// LCS (Longest Common Subsequence) 4         /// 
 5         private static string LCS(string str1, string str2) 6         {            7             var d = new int[str1.Length, str2.Length]; 8             var index = 0; 9             var length = 0;10             for (int i = 0; i < str1.Length; i++)11             {12                 for (int j = 0; j < str2.Length; j++)13                 {14                     var n = i - 1 >= 0 && j - 1 >= 0 ? d[i - 1, j - 1] : 0;  //左上角15                     d[i, j] = str1[i] == str2[j] ? 1 + n : 0; //当前节点值 = “1 + 左上角的值”：“0”16                     if (d[i, j] > length)  //如果是最大值，则记录该值和行号17                     {18                         length = d[i, j];19                         index = i;20                     }21                 }22             }23             return str1.Substring(index - length + 1, length);24         }25 26         /// 
27         /// 自己写的LCS,可求最大子串，最大串重复情况未考虑28         /// 
29         /// 30         /// 31         /// 
     32         private static string myLcs(string str1, string str2)33         {34             int[,] arr = new int[str1.Length, str2.Length];35             int max = 0;36             int maxIndex = 0;37             for (int i = 0; i < str1.Length; i++)38             {39                 for (int j = 0; j < str2.Length; j++)40                 {41                     if (str1[i] == str2[j])42                     {43                         arr[i, j] = (i > 0 && j > 0) ? (arr[i - 1, j - 1] + 1) : 1;44                         if (arr[i, j] > max)45                         {46                             max = arr[i, j];47                             maxIndex = i;48                         }49                     }50                 }51             }52 53             return str1.Substring(maxIndex - max + 1,max);54         }