黑马程序员技术交流社区

标题: 两个字符串中的最大相同子串练习 [打印本页]
作者: itheima_llt    时间: 2015-4-11 14:19
标题: 两个字符串中的最大相同子串练习
  1. /*
  2. 获取两个字符串中最大相同子串。第一个动作：将短的那个串进行长度一次递减的子串打印。
  3.         "abcwerthelloyuiodef"
  4.         "cvhellobnm"

  6. 模拟一下：
  7. 第一趟：
  8. 最大子串：cvhellobnm
  9.           ↑--------↑
  10. 在长字符串中查找
  11. abcwerthelloyuiodef
  12. ↑--------↑
  13. abcwerthelloyuiodef
  14. ↑--------↑
  15. abcwerthelloyuiodef
  16.   ↑--------↑
  17. abcwerthelloyuiodef
  18.    ↑--------↑
  19. abcwerthelloyuiodef
  20.     ↑--------↑
  21. abcwerthelloyuiodef
  22.      ↑--------↑
  23. abcwerthelloyuiodef
  24.       ↑--------↑
  25. abcwerthelloyuiodef
  26.        ↑--------↑
  27. abcwerthelloyuiodef
  28.         ↑--------↑
  29. abcwerthelloyuiodef
  30.          ↑--------↑
  31. 没有找到。
  32. 第二趟：
  33. 最大子串1：cvhellobnm
  34.            ↑-------↑
  35. 最大子串2：cvhellobnm
  36.             ↑-------↑
  37. 继续在长串中匹配，如果没有找到。
  38. 第三趟：
  39. 最大子串1：cvhellobnm
  40.            ↑------↑
  41. 最大子串2：cvhellobnm
  42.             ↑------↑
  43. 最大子串3：cvhellobnm
  44.              ↑------↑
  45. 继续在长串中匹配，如果没有找到。
  46. 第四趟：
  47. 最大子串1：cvhellobnm
  48.            ↑-----↑
  49. 最大子串2：cvhellobnm
  50.             ↑-----↑
  51. 最大子串3：cvhellobnm
  52.              ↑-----↑
  53. 最大子串4：cvhellobnm
  54.               ↑-----↑
  55. ······
  56. 如果找到了则停止，返回最大相同子串；
  57. 如果最大子串为""，则放回没有最大相同子串。

  59. 根据上面模拟过程，可以得到以下思路：
  60. 第一步：在两个字符串中选取长度短的那个字符串为key，长的那个为str；转到第二步。
  61. 第二步：从左到右，在str中匹配key，如果成功，转第四步；否则，转第三步。
  62. 第三步：将key长度减一，得到多个长度相同的子串，每个子串依次执行第二步。当key为空串的时候，转到第五步。
  63. 第四步：匹配成功，结束匹配。
  64. 第五步：匹配失败。

  66. 点评：第三步没有分析清楚，所以没有写出来。
  67. key.length()-0  子串1个
  68. key.length()-1  子串1+1个
  69. key.length()-2  子串1+1+1个
  70. key.length()-3  子串1+1+1+1个
  71. 可以观察发现，

  73. 第三步用大循环嵌套小循环实现。
  74. 大循环为key的
  75. */
  76. class getMaxSubstringDemo
  77. {
  78.         public static void main(String[] args)
  79.         {
  80.                 String str1 = "abcwerthelloyuiodef";
  81.                 String str2 = "cvhellobnm";

  83.                 System.out.println( getMaxSubstring(str1,str2));
  84.         }

  86.         //匹配最大相同子串
  87.         public static String getMaxSubstring(String str1,String str2)
  88.         {
  89.                 // 比较两个字符串长度，长的为str，短的为key
  90.                 String str = (str1.length()>str2.length())?str1:str2;
  91.                 String key = (str==str1)?str2:str1;
  92.                
  93.                 for(int i = 0;i < key.length(); i++)
  94.                 {
  95.                         for(int j = 0,k = key.length()-i; k !=key.length()+1;j++,k++)//j为key的头指针，k为key的尾指针
  96.                         {
  97.                                 //设置一个临时变量，存储最大相同子串
  98.                                 String temp = key.substring(j,k);
  99.                                 if(str.indexOf(temp) != -1)
  100.                                         return temp;
  101.                         }
  102.                 }
  103.                 return "";

  105.                
  106.                 /*错误思路，未解决问题
  107.                 //key在str中的位置
  108.                 int index = str.indexOf(key);

  110.                 /2 用方法int indexOf(String str)进行判断key是否被包含在str中
  111.                 当key不为空，且在str中没找到key时，执行循环。
  112.                 当key为空，就结束循环。
  113.                 当key不为空，inex!=-1时，说明找到了最大相同子串，停止循环。
  114.                 /
  115.                 while(key.length() != 0 && index ==-1)
  116.                 {
  117.                         index = str.indexOf(key);
  118.                 }

  120.                 //key的长度减一，得到多个相同长度的key
  121.                 public static String getKeySubstring(String key)
  122.                 {
  123.                         for(int i = 0;i < key.length(); i++)
  124.                         {
  125.                                 for(int j = 0;j < key.length()-i && j != key.length();)
  126.                         }
  127.                 }
  128.                 */
  129.        
  130.         }
  131. }
复制代码
思路还不是很清晰，暂时先这样了，等想清楚了，再写一遍！

两个字符串的相同子串练习.jpg (55.37 KB, 下载次数: 150)

两个字符串的相同子串练习.jpg
作者: sisel    时间: 2015-4-11 21:31
本帖最后由 sisel 于 2015-4-11 23:30 编辑

刚才的方法有2个漏洞 删除
用dp可以做到O(m*n) 级别的效率：

  2.         public static String maxSubString(String st1, String st2) {
  3.                 char[] x=st1.toCharArray(),y=st2.toCharArray();
  4.                 int maxlen =0, maxindex = 0,xlen=x.length,ylen=y.length;
  5.                 int [][] dp=new int[xlen][ylen];
  6.                 for (int i = 0; i < xlen; ++i) {
  7.                         for (int j = 0; j < ylen; ++j) {
  8.                                 if (x[i] == y[j]) {
  9.                                         if (i>0 && j>0) {
  10.                                                 dp[i][j] = dp[i - 1][j - 1] + 1;
  11.                                         }
  12.                                         if (i == 0 || j == 0) {
  13.                                                 dp[i][j] = 1;
  14.                                         }
  15.                                         if (dp[i][j] > maxlen) {
  16.                                                 maxlen = dp[i][j];
  17.                                                 maxindex = i + 1 - maxlen;
  18.                                         }
  19.                                 }
  20.                         }
  21.                 }
  22.                 return new String(x,maxindex,maxlen);
  23.         }
复制代码



作者: sisel    时间: 2015-4-11 21:59
我这个方法做了2重循环，效率还是很低 ，求高手
作者: lclxjzz    时间: 2015-4-11 22:04
看得头晕····
作者: itheima_llt    时间: 2015-4-12 21:56
{:3_46:}都来看看啊
作者: 晨间星光    时间: 2015-4-12 22:05
还没学到，了解一下
作者: llrs    时间: 2017-10-23 11:10
public class getString {

        public static void main(String[] args) {
               
                String str2 = "abcwerthelloyuiodef";
                String str1 = "cvhellobnm";
               
                getStr(str1, str2);
                       

        }

        public static void getStr(String str1, String str2) {
               
                String temp = null;
                //确保str1是较长的字符串，str2是较短的字符串
                if(str1.length()<str2.length())
                {
                        temp = str1;
                        str1 = str2;
                        str2 = temp;
                       
                }
                for(int i=str2.length();i>=0;i--) {
                        for(int j=0;j<=str2.length()-i;j++) {
                               
                                temp = str2.substring(j, j+i-1);
                                if(str1.contains(temp)) {
                                        System.out.println(str1+"和"+str2+"的最长字串是： "+temp);
                                        i = -1;  //跳出外循环
                                        break;
                                }
                        }
                }
               
//                System.out.println(str1+"和"+str2+"没有最长字串");
        }

}



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2