首页 > 试题广场 >

查找字符串最长公共子串

[编程题]查找字符串最长公共子串
  • 热度指数:2236 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
请编码实现一个命令行工具,找出指定的2个字符串的最长公共子串。

输入描述:
命令行工具接收两个字符串参数。输入字符串的合法字符集为[a-zA-Z0-9],大小写敏感,无需考虑异常输入场景。


输出描述:
所找到的公共子串;如果存在多个等长的公共子串,则请按字母序排序,依次打印出所有公共子串,每行一个。
示例1

输入

1234567 12893457

输出

345
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.HashMap;
import java.util.Iterator;
public class Main{
 public static void  main(String[] args){
        Scanner inPut = new Scanner(System.in);
        String str1 = inPut.next();
        String str2 = inPut.next();
        List<String> resultList = new LinkedList<String>();
//        System.out.println(str1.charAt(0));
        if(str1.length() !=0 && str2.length()!=0){
            for(int i =0;i<str1.length();i++){
                //遍历字符串一的所有字符
                char a = str1.charAt(i);
                for(int j=0;j<str2.length();j++){
                    if(str2.charAt(j) == a){
                        String temp = a+"";
                        if(i==str1.length()-1 || j ==str2.length()-1){
                            resultList.add(temp);
                        }else {
                            int k = 1;
                            while (k > 0 && k + i < str1.length() && k + j < str2.length()) {
                                if (str1.charAt(i + k) == str2.charAt(j + k)) {
                                    temp = temp + str1.charAt(i + k);
                                    k++;
                                } else {
                                    resultList.add(temp);
                                    k = -1;
                                }
                            }
                            resultList.add(temp);
                        }
                    }
                }
            }
            HashMap<String,Integer > outResult = new HashMap<>();
            for(String a: resultList){
                outResult.put(a,a.length());
            }
            Iterator iter = outResult.keySet().iterator();
            int maxIndex = -1;
            while (iter.hasNext()){
                String key = (String )iter.next();
                int value = outResult.get(key);
                if(value>maxIndex) maxIndex = value;
            }
            Iterator iter2 = outResult.keySet().iterator();
            while (iter2.hasNext()){
                String key = (String )iter2.next();
                int value = outResult.get(key);
                if(value==maxIndex) System.out.println(key);
            }
        }else {

        }
    }
}
输出结果顺序不一样,也会错?
发表于 2020-01-13 10:09:08 回复(0)