给定两个字符串,求字符串间的最长子字符串

发布网友发布时间：2022-04-22 13:42

共4个回答

热心网友时间：2022-04-22 15:12

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
*
* 不足：就是如果字符串过长，解析字符串势必花费时间多，比较相同字符串更费时间
* 漏洞：如果s1是"abcdef"，s2是"klbcadekl"时，相同的长字符串为"bc","de",而此程序只输出一个bc而已。自己改进吧
*
* QQgroup: two one seven seven seven one two 欢迎加入交流
*/
public class Test{

public static String checkEq(String s1,String s2){
  String maxEq = "";
  List<String> sub1 = new ArrayList<String>();//用于保存解析s1的所有可分成的子串
  List<String> sub2 = new ArrayList<String>();//用于保存解析s1的所有可分成的子串
  List<String> eqList = new ArrayList<String>();//保存相同的子串

  for(int i = 1;i<=s1.length();i++){//解析s1
   for(int j = 0;j<=s1.length()-i;j++){
    sub1.add(s1.substring(j,j+i));
    }
   }
  for(int i = 1;i<s2.length();i++){//解析s2
   for(int j = 0;j<=s2.length()-i;j++){
    sub2.add(s2.substring(j,j+i));
    }
   }
  //找到相同的字符串存到eqList中
  for(String s: sub1)
   if(sub2.contains(s))
    eqList.add(s);


  for (int i = 0; i < eqList.size(); i++) {//找出eqList中最长的
   String str = eqList.get(i);
   if(str.length()>maxEq.length()){
    maxEq = str;
   }
  }

  return maxEq;
}

public static  void main(String[] args){
  String s1 = "abcdef";
  String s2 = "klbcdekl";

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

  }
}

热心网友时间：2022-04-22 16:30

public static String LC(String a,String b){
String max = "";
for(int i=0;i<a.length();i++){
for(int j=0;j<a.length()-i;j++){
String tmp = a.substring(i, a.length()-j);
if(b.indexOf(tmp)>=0 && tmp.length()>max.length()){
max = tmp;
}
}
}
return max;
}

呀，已经有人回答了，而且还是一样的算法...呵呵

我来优化下吧

优化后的算法：

public static String LC(String a, String b) {
String min = b;
String max = a;
if (a.length() < b.length()) {
min = a;
max = b;
}
for (int i = 0; i < min.length(); i++) {
for (int j = 0; j <= i; j++) {
String tmp = min.substring(j, min.length() - i + j);
System.out.println(tmp);
if (max.indexOf(tmp) >= 0) {
return tmp;
}
}
}
return "";
}

前面算法时间复杂度永远是O(n^2)优化后的算法只有最坏情况是O(n^2)且n是a,b中较小的那个

如果存在不同的等长字符串，会返回最前面的那个比如abcdef和abasdec会返回ab而不会返回de

热心网友时间：2022-04-22 18:04

public String LC(String a,String b){
int maxLength=0;
String maxString="";
for(int i=0;i<a.length();i++){
for(int j=i+1;j<a.length()+1;j++){
String temp=a.substring(i, j);
int te=b.indexOf(temp);
if(te>-1 && temp.length()>maxLength){
maxLength=temp.length();
maxString=temp;
}
}
}
System.out.println("最长字符串是"+maxString);
return maxString;
}

试试这个代码

热心网友时间：2022-04-22 19:56