首页 > 试题广场 >

编写函数,获取两段字符串的最长公共子串的长度,例如:S1=

[问答题]
编写函数,获取两段字符串的最长公共子串的长度,例如:S1= GCCCTAGCCAGDE ,S2= GCGCCAGTGDE,这两个序列的最长公共子串是GCCAG。
public static String maxSame (String s1, String s2) {
    String subString = "";
    int start = 0;
    int end = 0;

    for (int i = 0; i < s2.length(); i++) {
        for (int j = i+1; j < s2.length(); j++) {
            if (j - i > end - start && s1.indexOf(s2.substring(i, j)) >=0 ) {
                start = s1.indexOf(s2.substring(i, j));
                end = start+j-i;
            }
        }
    }
    return subString=s1.substring(start,end);
}

发表于 2019-08-12 11:05:55 回复(0)
YL,头像 YL,
使用BF暴力匹配:
    private static String getMaxLenth(String s1, String s2) {

        String resultStr = "";

        if (s1.length() > s2.length()){
            return getMaxLenth(s2,s1);
        }

        for (int i = 0; i < s1.length(); i++) {
            for (int j = i; j <=s1.length() ; j++) {
                 String sub = s1.substring(i,j);

                 if (s2.contains(sub) && sub.length() > resultStr.length()){
                    resultStr = sub;
                 }
            }
        }

        return resultStr;
    }

发表于 2019-07-17 20:16:01 回复(0)