傻瓜笔记之动态规划(二)——最长公共子串

X = "abcopms"    Y = "opmkabc" , 最长公共子串Z = "abc   opm"

状态转移思路:由于记录的是最长的连续的子串,那么只需要在碰到相同的字符的时候做标记即可,不需要像最长子序列那样做状态转移的记录,即该问题的状态转换方程如下:

 

 

 

Z = 1,  z[i,j] = 0                     i==0 or j == 0

  2,  z[i,j] = z[i-1,j-1]+1     x[i] == y[j]    解1

  3,  z[i,j] = 0                     x[i]!=y[j]

 

解1:匹配到相同的字符的时候,就在两个字符串前面的基数上面增加1,意味着最长子串长度加一(到遍历的目前为止),这个是该方程唯一一个状态转移的过程。

下面贴上全文代码:

1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Threading.Tasks; 6 7 namespace 最长子串 8 { 9 class Program 10 { 11 public static string s1 = "abcopms"; 12 public static string s2 = "opmkabc"; 13 public static int maxLength = 0; // 记录最长的长度 14 public static int [,] c = new int[s1.Length+1, s2.Length+1]; 15 static void Main(string[] args) 16 { 17 MaxLength(); 18 for (int i = 0; i < s1.Length + 1; ++i) 19 { 20 for (int j = 0; j < s2.Length + 1; ++j) 21 { 22 Console.Write(c[i, j]); 23 } 24 Console.Write("\n"); 25 } 26 Console.WriteLine("这是所有子串"); 27 for(int i = 0;i<s1.Length+1;++i) 28 { 29 for(int j = 0;j<s2.Length+1;++j) 30 { 31 if (c[i, j] == maxLength) 32 { 33 Translate(i, j); 34 Console.Write("\n"); 35 } 36 } 37 } 38 Console.ReadKey(); 39 } 40 41 public static void Translate(int x,int y) 42 { 43 if (c[x, y] == 0) return; 44 else 45 { 46 Translate(x - 1, y - 1); 47 //Console.WriteLine("printf"); 48 Console.Write(s1[x - 1]); 49 } 50 } 51 52 public static int [,] MaxLength() 53 { 54 Console.WriteLine("这是状态矩阵"); 55 Console.WriteLine(s1); 56 Console.WriteLine(s2); 57 for(int i = 0;i<s1.Length+1;++i) 58 { 59 for(int j=0;j<s2.Length+1;++j) 60 { 61 if (i == 0 || j == 0) 62 c[i, j] = 0; 63 else if (s1[i-1] == s2[j-1]) 64 { 65 c[i, j] = c[i - 1, j - 1] + 1; 66 maxLength = Math.Max(maxLength, c[i, j]); 67 } 68 else 69 { 70 c[i, j] = 0; 71 } 72 } 73 } 74 return c; 75 } 76 } 77 }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zyjwyd.html