描述
查找两个字符串a,b中的最长公共子串。若有多个,输出在较短串中最先出现的那个。
注:子串的定义:将一个字符串删去前缀和后缀(也可以不删)形成的字符串。
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNextLine()) {
String str1 = sc.nextLine();
String str2 = sc.nextLine();
String minStr = str1;
String maxStr = str2;
if(minStr.length() > maxStr.length()) {
minStr = str2;
maxStr = str1;
}
// 找出str1的所有子串
List allSunStr = new ArrayList();
for (int i = 0; i < minStr.length(); i++) {
for (int j = i + 1; j <= minStr.length(); j++) {
allSunStr.add(minStr.substring(i, j));
}
}
// 排序将大的子串排在前面
Collections.sort(allSunStr, new Comparator() {
@Override
public int compare(String o1, String o2) {
return o2.length() - o1.length();
}
});
// 已经按最大到最小排序后就不用判断是否是最大子串,第一次匹配到的就是最大公共子串
for (int i = 0; i < allSunStr.size(); i++) {
if(maxStr.indexOf(allSunStr.get(i))> -1) {
System.out.println(allSunStr.get(i));
break;
}
}
}
}
}