java - 在 Java 中的字符串列表中查找公共子表达式的最有效方法

Question

我有一个代表包目录的字符串列表。我想迭代列表，找到包相同的字符串的最大部分，然后提取这个子字符串，从原始字符串列表中减去它以获得特定的包，以便创建适当的目录。

我正在考虑将原始列表创建为静态哈希集，然后使用 retainAll 方法，将结果存储在新字符串中。

像这样的东西会是性能最高的选择，还是有更好的方法来做到这一点？

非常感谢

Answer 1

这对我有用，评论中的解释

// returns the length of the longest common prefix of all strings in the given array 
public static int longestCommonPrefix(String[] strings) {
    // Null or no contents, return 0
    if (strings == null || strings.length == 0) {
        return 0;
        // only 1 element? return it's length
    } else if (strings.length == 1 && strings[0] != null) {
        return strings[0].length();
        // more than 1
    } else {
        // copy the array and sort it on the lengths of the strings,
        // shortest one first.
        // this will raise a NullPointerException if an array element is null 
        String[] copy = Arrays.copyOf(strings, strings.length);
        Arrays.sort(copy, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o2.length() - o1.length();
            }
        });
        int result = 0; // init result
        // iterate through every letter of the shortest string
        for (int i = 0; i < copy[0].length(); i++) { 
            // compare the corresponding char of all other strings
            char currenChar = copy[0].charAt(i);
            for (int j = 1; j < strings.length; j++) {                  
                if (currenChar != copy[j].charAt(i)) { // mismatch
                    return result;
                }
            }
            // all match
            result++;
        }
        // done iterating through shortest string, all matched.
        return result;
    }
}

如果更改原始数组不打扰您，则可以省略该行String[] copy = Arrays.copyOf(strings, strings.length);并仅对数组进行排序strings。

要检索文本，请将返回类型更改为并在循环内和方法末尾String返回类似的内容。return copy[0].substring(0, result + 1);return copy[0];

Answer 2

Just sort them. The common prefixes will appear first.

Answer 3

如果您只是在寻找一个最常见的软件包，我会执行以下操作：

从列表中获取第一个元素（称为参考包）。使用这个包名我会遍历列表。对于列表中的每个剩余元素，查看该元素是否包含参考包。如果是这样，请移至下一个元素。如果不将您的参考包修剪一个包（获取aa.bb.cc.serverside并转换为aa.bb.cc）。然后查看当前元素是否包含这个新的参考包。重复此操作，直到参考包为空或元素匹配。然后继续查看软件包列表。

这将为您提供最大最常见的软件包。通过从列表中的所有元素中删除它来循环返回。

编辑：稍作修改，最好保留.包名称的末尾以确保完整的包名称。