【Java】最长公共子串

喜欢ヅ旅行 2022-11-11 10:50 146阅读 0赞

Scanner in = new Scanner(System.in);
            while (in.hasNextLine()) { 
                String name1 = in.nextLine();
                String name2 = in.nextLine();
    
                int sum = calcSimilarity(name1, name2);
                System.out.println(sum);
            }
            
    
        public static String getMaxLengthCommonString(String s1, String s2) { 
            if (s1 == null || s2 == null)  { 
                return null;
            }
            a = s1.length();//s1长度做行
            b = s2.length();//s2长度做列
            if(a== 0 || b == 0) { 
                return "";
            }
            //设置匹配矩阵
            boolean [][] array = new boolean[a][b];
            for (int i = 0; i  < a; i++) { 
                char c1 = s1.charAt(i);
                for (int j = 0; j < b; j++) { 
                    char c2 = s2.charAt(j);
                    if (c1 == c2) { 
                        array[i][j] = true;
                    }  else { 
                        array[i][j] = false;
                    }
                }
            }
            //求所有公因子字符串，保存信息为相对第二个字符串的起始位置和长度
            List<ChildString> childStrings = new ArrayList<ChildString>();
            for (int i = 0; i < a; i++) { 
                getMaxSort(i, 0, array, childStrings);
            }
            for (int i = 1; i < b; i++) { 
                getMaxSort(0, i, array, childStrings);
            }
            //排序
            sort(childStrings);
            if (childStrings.size() < 1) { 
                return "";
            }
            //返回最大公因子字符串
            int max = childStrings.get(0).maxLength;
            StringBuffer sb = new StringBuffer();
            for (ChildString s: childStrings) { 
                if (max != s.maxLength) { 
                    break;
                }
                sb.append(s2.substring(s.maxStart, s.maxStart + s.maxLength));
            }
            return sb.toString();
        }
    
        //排序，倒叙
        private static void sort(List<ChildString> list) { 
            Collections.sort(list, new Comparator<ChildString>(){ 
                public int compare(ChildString o1, ChildString o2) { 
                    return o2.maxLength - o1.maxLength;
                }
            });
        }
    
        //求一条斜线上的公因子字符串
        private static void getMaxSort(int i, int j, boolean[][] array, List<ChildString> sortBean) { 
            int length = 0;
            int start = j;
            for (; i < a && j < b; i++,j++) { 
                if (array[i][j]) { 
                    length++;
                } else { 
                    sortBean.add(new ChildString(length, start));
                    length = 0;
                    start = j + 1;
                }
                if (i == a-1 || j == b-1) { 
                    sortBean.add(new ChildString(length, start));
                }
            }
        }
    
        //公因子类
        static class ChildString { 
            int maxLength;
            int maxStart;
    
            ChildString(int maxLength, int maxStart){ 
                this.maxLength = maxLength;
                this.maxStart = maxStart;
            }
        }