黑马程序员技术交流社区

标题: 获取两个字符串的最大相同子串. [打印本页]

作者: HM何伟 时间: 2013-4-5 23:15
标题: 获取两个字符串的最大相同子串.
有没有更简单明了的方法, 获取两个字符串的最大相同子串。
希望不要是毕老师的那种方法.

作者: Lobster 时间: 2013-4-6 00:25
{:soso_e199:}忘记毕老师是怎么写的了，我自己写的话，不考虑算法时间复杂度就这样吧

public static void main(String[] args){
System.out.println(getSame("121381123211213875888","121387"));
}
//找最大子字符串
public static String getSame(String s1,String s2){
//以s1为基准在s2中寻找s1的子串
int len = s1.length();
for(int i = len;i>1;i--){
for(int s=0,e=i;e<=len;s++,e++){
//这里从长到短获取s1的所有子串进行判断
if(s2.contains(s1.substring(s,e))) {
return s1.substring(s,e);
}
}
}
//无重复返回空
return null;
}

复制代码

作者: 张洪慊 时间: 2013-4-6 01:43

Lobster 发表于 2013-4-6 00:25
忘记毕老师是怎么写的了，我自己写的话，不考虑算法时间复杂度就这样吧 ...

针对楼上,说个小细节.
for(int i = len;i>1;i--)//i>=1
由于substring包含头不包含尾
当i=1时,即e=1
substring(0,1),substring(1,2).......
也就是说截取只含有一个字符的字符串.

作者: 刘吉庆 时间: 2013-4-6 07:58

public class StringTest3 {
public static void main(String[] args) {
String s1 = "sadabcdfghjkl";
String s2 = "werabcdtyu";
// 写一个功能，返回一个子串
String subString = getSubString(s1, s2);
System.out.println("两个串中的最大子串是:"+subString);
}
private static String getSubString(String s1, String s2) {
// 如果得到s1和s2中的较大的串呢
String maxString, minString;
// 通过三元运算符得到较大的字符串赋值给maxString
maxString = s1.length() > s2.length() ? s1 : s2;
// 得到较小的串
minString = (maxString.equals(s1)) ? s2 : s1;
// System.out.println(maxString+"***"+minString);
for (int x = 0; x < minString.length(); x++) {
for (int start = 0, end = minString.length() - x; end <= minString.length(); start++, end++) {
String temp = minString.substring(start, end);
if (maxString.contains(temp)) {
return temp;
}
}
}
//如果没有找到，说明没有相同的字符
return null;
}
}

复制代码

楼主，这个效率会稍微高一点：请参考

作者: 刘策 时间: 2013-4-6 09:54
本帖最后由刘策于 2013-4-6 18:12 编辑

import java.util.*;
class Test{
public static void main(String[] args){
String str = "sadabcdfwojdifshfkgghjkl";
String strr = "kdfskdfsdfshdfjskdf";
System.out.println("子串："+trans(strr,str));
}
//将字符转为字符数组，将其存入集合中，
public static String trans(String str,String strr){
ArrayList<Character> al = new ArrayList<Character>();
ArrayList<Character> all = new ArrayList<Character>();
char[] chs= str.toCharArray() ;
char[] chss = strr.toCharArray();
for(int x = 0; x<str.length();x++){
al.add(chs[x]);
}
for(int y=0; y<strr.length();y++){
all.add(chss[y]);
}
//取交集。
al.retainAll(all);
//保证元素唯一。
return single(al);
}
//保证元素的唯一性
public static String single(ArrayList<Character> al){
ArrayList<Character> chal = new ArrayList<Character>();
for(ListIterator<Character> li= al.listIterator(); li.hasNext();){
Character c = li.next();
if(!(chal.contains(c)))
chal.add(c);
}
Character[] a = new Character[chal.size()];
return Arrays.toString( chal.toArray(a));
}
}
刚学到集合，就用集合的知识写了一个，这个程序不太健壮，仅供参考，用集合完成也许有点大材小用，

复制代码

作者: 杨武林 时间: 2013-4-6 13:07
/**

   “abcwerthelloyuiodef”  "cvhellobnm"

      思路：

   1、将短的那个子串按照长度递减的方式获取到。

   2、将每获取到的子串去长串中判断是否包含，如果包含，已经找到

*/

public class getMaxSubString {

public static void main(String[] args) {

   String s1 = "abcwerthelloyuiodef";

   String s2 = "cvhellobnm";

   System.out.println(getMaxSubString1(s1,s2));

}

public static String getMaxSubString1(String s1,String s2){

   String max = "";

   String min = "";

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

   min = (max == s1) ? s2:s1;

   System.out.println("max="+max+"...."+"min="+min);

   for(int x=0;x<min.length();x++){

         for(int y=0,z=min.length()-x;z!=min.length()+1;y++,z++){

            String temp = min.substring(y,z);

            if(max.contains(temp))

               return temp;

         }

   }

   return "";

}

}

作者: 陈丽莉 时间: 2013-4-6 18:24
追问或结贴哦~ 至少给回答的人一个回复，让大家知道你在看~

作者: HM何伟 时间: 2013-4-6 21:10

刘策发表于 2013-4-6 09:54

还是这个看的更清晰/

作者: 张弗睿 时间: 2016-10-27 00:38
厉害了word哥

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

黑马程序员IT技术论坛 X3.2