Java：求两个字符串的所有公共子串

迷南。 2023-10-05 20:31 4阅读 0赞

要求：求两个字符串的所有公共子串，如“abcdefgad”和“adefgwgewegad”的公共子串为“defg”、“ad”（子串必须是连续不重合的且长度大于1）

# 求两个字符串的所有公共子串 #

## 方法一： ##

1.  对于较短的那个字符串，假设其长度为n，依次找到它的长度为n, n-1, n-2....1的若干的子串；
2.  若另外那个较长的字符串包含了较短字符串的某个子串，则找到了二者的最长公共子串；
3.  将两个字符串都剔除掉最长公共子串，然后再寻找下一个最长公共子串；

/**
         *  获取两个字符串中所有相同子串。
         */
        public static List<String> maxSub1(String s1, String s2){
            List<String> result = new ArrayList<>();
            String max="",min="";
    
            max = (s1.length() > s2.length()) ? s1 : s2;
            min = (max == s1) ? s2 : s1;
    
            for(int x = 0; x < min.length(); x++){
                for(int y = min.length() ; y > x ; y--){
                    String temp = min.substring(x, y);
                    if(max.contains(temp) && temp.length()>1){
                        result.add(temp);
                        min = getSpitText(temp,min);
                        max = getSpitText(temp,max);
                        break;
                    }
                }
            }
            return result;
        }
    
        private static String getSpitText(String temp,String text) {
            Integer start = text.indexOf(temp);
            Integer end = start + temp.length();
            String minStartPart = text.substring(0,start);
            String minEndPart = text.substring(end,text.length());
            text = minStartPart + " " + minEndPart;
            return text;
        }

## 方法二： ##

采用动态规划的思想：用一个二维矩阵来记录中间结果，矩阵的横坐标为字符串1的各个字符，矩阵的纵坐标为字符串2的各个字符。

举例说明：假设两个字符串分别为"bab"和"caba" (当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")

b　　a　　b

c　　0　　0　　0

a　　0　　1　　0

b　　1　　0　　1

a　　0　　1　　0

可以看出，矩阵的斜对角线最长的那个就对应着两个字符串的最长公共子串。

不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事，可以用下面的方法改进：当要在矩阵是填1时让它等于其左上角元素加1。

b　　a　　b

c　　0　　0　　0

a　　0　　1　　0

b　　1　　0　　2

a　　0　　2　　0

这样矩阵中的最大元素就是最长公共子串的长度。另外，在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了，所以实际上在程序中可以用一维数组来代替这个矩阵。

/**
         *  获取两个字符串中最长相同子串。
         */
        public static List<String> maxSub2(String s1, String s2){
            List<String> result = new ArrayList<>();
            String max="",min="";
    
            max = (s1.length() > s2.length()) ? s1 : s2;
            min = (max == s1) ? s2 : s1;
            while (true){
                String same = maxSubstring(max,min);
                if (CommonTools.isEmpty(same)||same.length()==1)
                    break;
                result.add(same);
                min = getSpitText(same,min);
                max = getSpitText(same,max);
            }
            return result;
        }
    
        // 求解两个字符号的最长公共子串
        public static String maxSubstring(String strOne, String strTwo){
            // 参数检查
            if(strOne==null || strTwo == null){
                return null;
            }
            if(strOne.equals("") || strTwo.equals("")){
                return null;
            }
            // 矩阵的横向长度
            int len1 = strOne.length();
            // 矩阵的纵向长度
            int len2 = strTwo.length();
    
            // 保存矩阵的上一行
            int[] topLine = new int[len1];
            // 保存矩阵的当前行
            int[] currentLine = new int[len1];
            // 矩阵元素中的最大值
            int maxLen = 0;
            // 矩阵元素最大值出现在第几列
            int pos = 0;
            char ch = ' ';
            for(int i=0; i<len2; i++){
                ch = strTwo.charAt(i);
                // 遍历str1，填充当前行的数组
                for(int j=0; j<len1; j++){
                    if( ch == strOne.charAt(j)){
                        // 如果当前处理的是矩阵的第一列，单独处理，因为其坐上角的元素不存在
                        if(j==0){
                            currentLine[j] = 1;
                        } else{
                            currentLine[j] = topLine[j-1] + 1;
                        }
                        if(currentLine[j] > maxLen){
                            maxLen = currentLine[j];
                            pos = j;
                        }
                    }
                }
                // 将矩阵的当前行元素赋值给topLine数组; 并清空currentLine数组
                for(int k=0; k<len1; k++){
                    topLine[k] = currentLine[k];
                    currentLine[k] = 0;
                }
                // 或者采用下面的方法
                // topLine = currentLine;
                // currentLine = new int[len1];
            }
            return strOne.substring(pos-maxLen+1, pos+1);
        }

## 测试： ##

public static void main(String[] args) throws IOException {
            // 输入
            String str1 = "abcdefgad";
            String str2 = "adefgwgewegad";
    
            System.out.println("相同的字符: " );
            System.out.println(maxSub1(str1,str2));
            System.out.println(maxSub2(str1,str2));
        }

## 结果： ##

> 相同的字符:
> 
> \[defg, ad\]  
> \[defg, ad\]