有没有更简单明了的方法, 获取两个字符串的最大相同子串。
希望不要是毕老师的那种方法.

厉害了word哥

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

还是这个看的更清晰/

追问或结贴哦~  至少给回答的人一个回复，让大家知道你在看~

/**

       “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 "";

    }

}

1. import java.util.*;
   
2. class Test{
   
3.         public static void main(String[] args){
   
4.                
   
5.                 String str = "sadabcdfwojdifshfkgghjkl";
   
6.                 String strr = "kdfskdfsdfshdfjskdf";
   
7.                 System.out.println("子串："+trans(strr,str));
   
8.         }        
   
9.         //将字符转为字符数组，将其存入集合中，
   
10.         public static String trans(String str,String strr){
    
11.                 ArrayList<Character> al  = new ArrayList<Character>();
    
12.                 ArrayList<Character> all = new ArrayList<Character>();
    
13.                         char[] chs= str.toCharArray()        ;
    
14.                         char[] chss = strr.toCharArray();
    
15.                 for(int x = 0; x<str.length();x++){
    
16.                         al.add(chs[x]);
    
17.                         
    
18.                 }
    
19.                 for(int y=0; y<strr.length();y++){
    
20.                         all.add(chss[y]);        
    
21.                 }
    
22.                 //取交集。
    
23.                 al.retainAll(all);
    
24.                 //保证元素唯一。
    
25.                 return single(al);
    
26.         
    
27.         }
    
28.         //保证元素的唯一性
    
29.         public static String single(ArrayList<Character> al){
    
30.         ArrayList<Character> chal = new ArrayList<Character>();
    
31. 
    
32.                 for(ListIterator<Character>  li= al.listIterator(); li.hasNext();){
    
33.                         Character c = li.next();
    
34.                                 if(!(chal.contains(c)))
    
35.                                         chal.add(c);                        
    
36.                 }
    
37.                 Character[] a = new Character[chal.size()];
    
38.                
    
39.                  return Arrays.toString( chal.toArray(a));
    
40.                
    
41.         }
    
42. }
    
43. 刚学到集合，就用集合的知识写了一个，这个程序 不太健壮，仅供参考，用集合完成也许有点大材小用，

复制代码

1. public class StringTest3 {
   
2.         public static void main(String[] args) {
   
3.                 String s1 = "sadabcdfghjkl";
   
4.                 String s2 = "werabcdtyu";
   
5. 
   
6.                 // 写一个功能，返回一个子串
   
7.                 String subString = getSubString(s1, s2);
   
8.                 System.out.println("两个串中的最大子串是:"+subString);
   
9.         }
   
10. 
    
11.         private static String getSubString(String s1, String s2) {
    
12.                 // 如果得到s1和s2中的较大的串呢
    
13.                 String maxString, minString;
    
14.                 // 通过三元运算符得到较大的字符串赋值给maxString
    
15.                 maxString = s1.length() > s2.length() ? s1 : s2;
    
16.                 // 得到较小的串
    
17.                 minString = (maxString.equals(s1)) ? s2 : s1;
    
18.                 // System.out.println(maxString+"***"+minString);
    
19. 
    
20.                 for (int x = 0; x < minString.length(); x++) {
    
21.                         for (int start = 0, end = minString.length() - x; end <= minString.length(); start++, end++) {
    
22.                                 String temp = minString.substring(start, end);
    
23.                                 if (maxString.contains(temp)) {
    
24.                                         return temp;
    
25.                                 }
    
26.                         }
    
27.                 }
    
28.                 //如果没有找到，说明没有相同的字符
    
29.                 return null;
    
30.         }
    
31. }

复制代码

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

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).......
也就是说截取只含有一个字符的字符串.

{:soso_e199:}忘记毕老师是怎么写的了，我自己写的话，不考虑算法时间复杂度就这样吧

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

复制代码