黑马程序员技术交流社区

标题: 给定两个字符串，获取两个字符串中最大相同的子串. [打印本页]
作者: Beipiaoshiguang    时间: 2015-4-6 00:10
标题: 给定两个字符串，获取两个字符串中最大相同的子串.
String str = "abstractfistreamleoutput";                  //stream
String newstr = "maeetstuptuoestreamliftcartsba";//stream
看到这个题目,我首先想到了切割功能,但是仔细一酝酿感觉不对劲.我希望校友能给我一些思路。


作者: 邓士林    时间: 2015-4-6 00:10
这题，有个算法就是利用动态规划进行解答，有点难度。最差的算法就是通过遍历统计出每次的字符串，找到最大的字符串，然后输出。
package com.dsw.test;

public class CalculateMaxString {

        public static void main(String[] args) {
                String src = "abstractfistreamleoutput";
                String tar = "maeetstuptuoestreamliftcartsba";
                char [] srcCh = src.toCharArray();
                char [] tarCh = tar.toCharArray();
                int count = 0;
                int max = 0;
                StringBuilder sb = null;
                String maxString = null;
                for(int i=0;i<srcCh.length;i++)
                        for(int j=0;j<tarCh.length;j++){
                                sb = new StringBuilder();
                                int k=j;
                                int m = i;
                                count = 0;
                                while(srcCh[m] == tarCh[k]){
                                        count++;
                                        sb.append(tarCh[k]);
                                        k++;
                                        m++;
                                        if(m == srcCh.length || k == tarCh.length)break;
                                }
                                if(count > max){//统计最大的字符串
                                        max = count;
                                        maxString = sb.toString();
                                }
                        }
                System.out.println("原字符串:" + src);
                System.out.println("子字符串:" + tar);
                System.out.println(maxString);
        }
}

代码我写的就这样，效率差，凑合看吧！
原字符串:abstractfistreamleoutput
子字符串:maeetstuptuoestreamliftcartsba
streaml

作者: AsyncTask    时间: 2015-4-6 15:04
我的思路：
作者: AsyncTask    时间: 2015-4-6 15:10
思路：
1.首先判断两字符串长度，哪个是较长的，哪个是较短的。
2.获取较短字符串的所有子串，子串的长度从较短的字符串的长度开始递减到1来遍历
3.判断较长字符串是否含有子串，如果有则说明是最大子串，否则继续遍历
不知是否能说明白。
作者: ZSMAN    时间: 2015-4-6 17:06
  1. public static String getMaxSubString(String s1,String s2)
  2.         {

  4.                 String max = "",min = "";

  6.                 max = (s1.length()>s2.length())?s1: s2;

  8.                 min = (max==s1)?s2: s1;
  9.                
  10. //                sop("max="+max+"...min="+min);
  11.                 for(int x=0; x<min.length(); x++)
  12.                 {
  13.                         for(int y=0,z=min.length()-x; z!=min.length()+1; y++,z++)
  14.                         {
  15.                                 String temp = min.substring(y,z);
  16.                                
  17.                                 sop(temp);
  18.                                 if(max.contains(temp))//if(s1.indexOf(temp)!=-1)
  19.                                         return temp;
  20.                         }
  21.                 }
  22.                 return "";
  23.         }
复制代码
作者: woshixtdx    时间: 2015-4-6 19:44
毕老师视频里面有
作者: zero-xiao    时间: 2015-4-6 19:59
这不是基础测试最后一题
作者: Beipiaoshiguang    时间: 2015-4-6 20:38
AsyncTask 发表于 2015-4-6 15:10
思路：
1.首先判断两字符串长度，哪个是较长的，哪个是较短的。
2.获取较短字符串的所有子串，子串的长度从 ...

定义一个方法,先获取一个字符串中出现最长的子字符串
再拿该子字符串与要比较的字符串相比较(问题在于两个字符串同时比较,两者相同,且返回子字符串最长),我要是两个字符串同时比较该如何去使用呢？
作者: Beipiaoshiguang    时间: 2015-4-6 20:41
woshixtdx 发表于 2015-4-6 19:44
毕老师视频里面有

我之前下载了毕姥爷的视频,然后因为电脑磁盘空间太小,于是便把它删除了. 我待会儿去下载看看。
作者: 杨大萌    时间: 2015-4-6 20:41
用包含contains来做。
作者: Beipiaoshiguang    时间: 2015-4-6 20:42
ZSMAN 发表于 2015-4-6 17:06

提示码里面也包含了你代码中一条语句,死活就是想不到那个点上去。
作者: Beipiaoshiguang    时间: 2015-4-6 20:46
ZSMAN 发表于 2015-4-6 17:06

该sop是哪里来的？
作者: Beipiaoshiguang    时间: 2015-4-6 20:50
能写一下注释给我吗？
作者: Beipiaoshiguang    时间: 2015-4-6 20:54
杨大萌 发表于 2015-4-6 20:41
用包含contains来做。

尝试过了,行不通
作者: 杨大萌    时间: 2015-4-6 20:56
代码复制过来，contains可以的，两个for循环就ok了
作者: Beipiaoshiguang    时间: 2015-4-6 21:00
杨大萌 发表于 2015-4-6 20:56
代码复制过来，contains可以的，两个for循环就ok了

{:3_56:} 老兄,我不会,能教教我吗？
作者: AsyncTask    时间: 2015-4-6 21:59
Beipiaoshiguang 发表于 2015-4-6 20:38
定义一个方法,先获取一个字符串中出现最长的子字符串
再拿该子字符串与要比较的字符串相比较(问题在于两 ...

下面是我的实现，就是遍历所有的，有空再看看动态规划的实现。

  1. class StringTool {
  2.         //求最大子串的方法
  3.         public static List<String> maxStrings(String a, String b) {
  4.                 //用于存放找到的最大子串的list
  5.                 List<String> maxString = new ArrayList<String>();
  6.                 //首先判断a,b字符串哪个为长字符串，哪个为端字符串
  7.                 String longString = a.length() > b.length() ? a : b;
  8.                 String shortString = a.length() < b.length() ? a : b;
  9.                 //从端字符串的最长子串开始遍历，判断长字符串是否包括该子串
  10.                 //最长子串的从较短的字符串的长度递减遍历
  11.                 for (int len = shortString.length(); len > 0; len--) {
  12.                         //以当前的子串长度为基础，从0下标开始遍历判断
  13.                         for (int start = 0; start + len <= shortString.length(); start++) {
  14.                                 //获取当前长度的子串
  15.                                 String subString = shortString.substring(start, start + len);
  16.                                 //如果包括则加入list中
  17.                                 if (longString.contains(subString)) {
  18.                                         maxString.add(subString);
  19.                                 }
  20.                         }
  21.                         //如果该轮过后找到，就说明为已找到最大的公共子串，可能过含有多个，那就直接退出
  22.                         if (!maxString.isEmpty()) {
  23.                                 break;
  24.                         }
  25.                 }
  26.                 return maxString;
  27.         }
  28. }
复制代码
作者: 马丁    时间: 2015-4-8 09:58
受教了，比我想的简单多了



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