如何找到字符串中最常见的部分？

Question

假设我们有一个字符串集合。

asList("abcdxyz", "abcdyz", "abcdm", "abcdn", "abcdo");

我们如何仅使用字符串 class 方法找到最常见的部分 "abcd"？

Answer 1

这被称为 longest common substring problem and has been the subject of some research (also see the longest common subsequence problem)。您应该阅读问题，然后实施适当的算法。

我没有时间实现完整的算法，但我发现 this blog post 有一个实现。

Answer 2

对于这种特定情况，您可以开始比较子字符串，在每次传递中增加子字符串的长度

Answer 3

您可能正在寻找 Longest Common Substring 问题（对于 n 个字符串）。

您可以使用此代码作为开始，但代码可能会抓取较大的 'n' 值。在那种情况下，你最好使用动态规划[参见相关部分here]。

public static String identifyCommonSubStrOfNStr(String [] strArr){

    String commonStr="";
    String smallStr ="";        

    //identify smallest String      
    for (String s :strArr) {
        if(smallStr.length()< s.length()){
            smallStr=s;
        }
    }

    String tempCom="";
    char [] smallStrChars=smallStr.toCharArray();               
    for (char c: smallStrChars){
        tempCom+= c;

        for (String s :strArr){
            if(! s.contains(tempCom)){
            tempCom="";
                break;
            }               
        }

        if(tempCom!="" && tempCom.length()>commonStr.length()){
            commonStr=tempCom;  
        }                       
    }   

    return commonStr;
}

注意：最长公共子串问题不同于最长公共Subsequence问题，因为与子串不同，子序列不需要占据原始序列中的连续位置。

希望对您有所帮助！

如何找到字符串中最常见的部分？

How to find the most common part of a string?

java

string

core