最长公共子序列与最长连续公共子序列-Java

柔情只为你懂 2021-11-23 02:50 337阅读 0赞

### 最长公共子序列与最长连续公共子序列（java） ###

### 1、最长公共子序列，顺序是一致并且相等，但是字符之间可以不是连续的。 ###

### 2、求最长公共字符串，这就要求既是公共的字符串，又需要是连续的。 ###

> 1.  package pratice725;
> 2.  //最长公共子序列与最长连续公共子序列（java）
> 3.  //顺序是一致并且相等，但是字符之间可以不是连续的。
> 4.  public class findLCS \{
> 5.      public static void findLCS(String str,String patt)\{
> 6.          int strl = str.length();
> 7.          int pattl = patt.length();
> 8.          int lcs\[\]\[\] = new int\[strl\]\[pattl\];
> 9.          char strc\[\] = str.toCharArray();
> 10.         char pattc\[\] = patt.toCharArray();
> 11.         
> 12.         if(str==null || strl==0 || patt==null || pattl==0) return;
> 13.         int t = 0;
> 14.         for(int i =0;i<strl;i++)\{
> 15.             if(strc\[i\]==pattc\[0\])
> 16.             \{
> 17.                 t = 1;
> 18.             \}
> 19.             lcs\[i\]\[0\]=t;
> 20.         \}
> 21.         t = 0;
> 22.         for(int j=0;j<pattl;j++)\{
> 23.             if(strc\[0\]==pattc\[j\])\{
> 24.                 t = 1;
> 25.             \}
> 26.             lcs\[0\]\[j\] = t;
> 27.         \}
> 28.         for(int i=1;i<strl;i++)\{
> 29.             for(int j=1;j<pattl;j++)
> 30.             \{
> 31.                 if(strc\[i\]==pattc\[j\])\{
> 32.                     lcs\[i\]\[j\] = lcs\[i-1\]\[j-1\]+1;
> 33.                 \}else\{
> 34.                     lcs\[i\]\[j\] = Math.max(lcs\[i-1\]\[j\], lcs\[i\]\[j-1\]);
> 35.                 \}
> 36.             \}
> 37.         \}
> 38.         System.out.println("最大公共子序列长度矩阵是： ");
> 39.         for(int i=0;i<strl;i++)\{
> 40.             for(int j=0;j<pattl;j++)
> 41.             \{
> 42.                 System.out.print(lcs\[i\]\[j\]+" ");
> 43.             \}
> 44.             System.out.println("");
> 45.         \}
> 46.         System.out.println("最大公共子序列长度是： "+lcs\[strl-1\]\[pattl-1\]);
> 47.     \}
> 48. //求最长公共字符串，这就要求既是公共的字符串，又需要是连续的。    
> 49.     public static void getLCSString(String str,String patt)\{
> 50.         int strl = str.length();
> 51.         int pattl = patt.length();
> 52.         int lcs\[\]\[\] = new int\[strl\]\[pattl\];
> 53.         char strc\[\] = str.toCharArray();
> 54.         char pattc\[\] = patt.toCharArray();
> 55.         
> 56.         if(str==null || strl==0 || patt==null || pattl==0) return;
> 57.         int t = 0;
> 58.         for(int i =0;i<strl;i++)\{
> 59.             if(strc\[i\]==pattc\[0\])
> 60.             \{
> 61.                 t = 1;
> 62.             \}else\{
> 63.                 t=0;
> 64.             \}
> 65.             lcs\[i\]\[0\]=t;
> 66.         \}
> 67.         t = 0;
> 68.         for(int j=0;j<pattl;j++)\{
> 69.             if(strc\[0\]==pattc\[j\])\{
> 70.                 t = 1;
> 71.             \}else\{
> 72.                 t=0;
> 73.             \}
> 74.             lcs\[0\]\[j\] = t;
> 75.         \}
> 76.         for(int i=1;i<strl;i++)\{
> 77.             for(int j=1;j<pattl;j++)
> 78.             \{
> 79.                 if(strc\[i\]==pattc\[j\])\{
> 80.                     lcs\[i\]\[j\] = lcs\[i-1\]\[j-1\]+1;
> 81.                 \}else\{
> 82.                     lcs\[i\]\[j\] = 0;
> 83.                 \}                    
> 84.             \}
> 85.         \}
> 86.         System.out.println("最大公共子串矩阵是： ");
> 87.         for(int i=0;i<strl;i++)\{
> 88.             for(int j=0;j<pattl;j++)
> 89.             \{
> 90.                 System.out.print(lcs\[i\]\[j\]+" ");
> 91.             \}
> 92.             System.out.println("");
> 93.         \}
> 94.     \}
> 95.     public static void main(String\[\] args) \{
> 96.         String str = "android";
> 97.         String patt = "random";
> 98.         findLCS(str,patt);
> 99.         System.out.println("");
> 100.         getLCSString(str,patt);
> 101.     \}
> 102. \}

**扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20211122/a447e5cf8e274923bed40fe77f592a2d.png