题解 | #查找两个字符串a,b中的最长公共子串#

初见这道题想的很难，比如动态规划算法。

但是仔细观察以后，发现有点类似于数据库中的Nested Loop的思想，无非是用一张表驱动另一张表，循环找想要的东西而已。

用图来说明，就是将短的字符串从右向左遍历截取，看看截取的结果在不在长串中，如果在就保存下来，如果不在就继续截取。

当左右指针i和k相遇时，开始下一趟，k归位到最右，i++。以此类推。

alt

最后，将保存的结果按长短排序，打印最长的：


import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String a = in.nextLine();
            String b = in.nextLine();
            String longStr;
            String shortStr;
            if (a.length() > b.length()) {
                longStr = a;
                shortStr = b ;
            } else {
                longStr = b;
                shortStr = a;
            }
            List<String> list = new ArrayList<>();
            for (int i = 0; i < shortStr.length(); i++) {
                for (int k = shortStr.length(); i < k ; k--) {
                    if (longStr.contains(shortStr.substring(i, k))) {
                        list.add(shortStr.substring(i, k));
                    }
                }
            }
            list.sort((o1, o2) -> o2.length() - o1.length());
            System.out.println(list.get(0));
        }
    }
}

但是这段代码在执行的时候，我发现list里充斥大量的元素，因此我想我的解法应该很慢，而且空间占用很多。

进一步思考我发现每次匹配的时候，如果引入一个长度变量记录上一次的子串长度，当下一次子串比上一次更长的时候才记录到list里，岂不是很好，于是代码优化了一下：

package huawei;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String a = in.nextLine();
            String b = in.nextLine();
            String longStr;
            String shortStr;
            if (a.length() > b.length()) {
                longStr = a;
                shortStr = b ;
            } else {
                longStr = b;
                shortStr = a;
            }
            List<String> list = new ArrayList<>();
            int maxLength = 0;
            for (int i = 0; i < shortStr.length(); i++) {
                for (int k = shortStr.length(); i < k ; k--) {
                    int length = shortStr.substring(i, k).length();
                    if (longStr.contains(shortStr.substring(i, k)) && maxLength < length) {
                        list.add(shortStr.substring(i, k));
                        maxLength = length;
                    }
                }
            }
            list.sort((o1, o2) -> o2.length() - o1.length());
            System.out.println(list.get(0));
        }
    }
}

从代码的执行情况来看，确实有效果：

alt