0

我编写了以下 Java 代码来搜索一对字符串之间共有的最长子字符串。代码如下：

public static void main(String[] args) {
        // TODO code application logic here
        String cad1="xyzdistancerttp";
        String cad2="abcxtwndistattttt";
        String seq, lcs;   
        seq="";
        lcs="";
        System.out.println(cad1.length());
        for (int i=0;i<cad1.length();i++){
            for (int j=0;j<cad2.length();j++){
                if (cad1.charAt(i)==cad2.charAt(j)){
                    seq=seq+cad1.charAt(i);
                    i++;
                }
                else{
                    if (seq.length()>lcs.length()){
                        lcs=seq;
                        seq="";
                    }
                }
            } 
        }
        System.out.println(lcs);
    }

当我用这些字符串测试它时，程序返回正确的字符串 dist，但是当我将字符串更改为：

String cad1="xyzdistancerttt";
String cad2="abcxtwndistattttt";

我得到一个索引越界异常。还进行了以下更改：

String cad1="xyzdistancertttttp";
String cad2="abcxtwndistatttttsss";

结果我得到了字符串cttttt，但它应该只打印ttttt。有什么帮助吗？

谢谢

4

3 回答 3

0

方法longestEqualSubstring需要两个字符串来找到最长相等的 sustring。它需要 1 个字符s1并将其与 的每个字符进行比较s2。如果两个字符相等，则进入while循环比较下一个字符，s1并将s2相等的字符存储在current变量中。如果current的长度大于前一个相等的子字符串，longest则变为current。

private static String longestEqualSubstring(String s1, String s2) {
        String longest = "", current = "";
        for (int i = 0; i < s1.length(); i++)
            for (int j = 0; j < s2.length(); j++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    int ii = i, jj = j;
                    while (ii < s1.length() && jj < s2.length() && s1.charAt(ii) == s2.charAt(jj)) {
                        current += s1.charAt(ii);
                        ii++;
                        jj++;
                    }
                    if (current.length() > longest.length())
                        longest = current;
                    current = "";
                }
            }
        return longest;
    }

主要测试方法：

public static void main(String[] args) {
        String cad1 = "xyzdistancerttttttp";
        String cad2 = "abcxtwndistancetttttttttttttttttttttttss";

        String longestEqualSubstring = longestEqualSubstring(cad1, cad2);
        System.out.println(longestEqualSubstring);
    }

印刷 ：

distance
于 2017-05-01T15:10:48.823 回答
0

我看到有两件事出了问题。

——问题之一在于

if (cad1.charAt(i)==cad2.charAt(j)){
     seq=seq+cad1.charAt(i);
     i++;
}

正如 M2E67 在他的第二个实现中所展示的，您需要检查是否i超出范围，如果超出则跳过比较。举个例子：对于你的第一组字符串，wheni = cad1.length-1和j = cad2.length-2，它将添加一个到i， make i = cad1.length，并cad1.charAt(i)在 for 循环的下一次迭代中执行——这会引发 ArrayIndexOutOfBounds 异常。

--第二个问题是您没有检查两个子字符串之间的每个可能的子字符串。在您的代码中，您每次都在跳过一个可能的起始索引i++。我会在 cad1 中选择一个起点，在 cad2 中选择一个起点，找到这些起始索引的共同字符数，然后选择下一对起始索引（在 M2E67 的代码中也有说明）。

至于 cttttt 输出，我不确定发生了什么。

于 2017-04-26T06:26:54.743 回答
0

这是计算机科学中一个非常重要的算法问题，就像最长公共子串问题一样。你可以找到这个算法的几个实现。例如使用以下代码：

实施1：

public static int longestSubstr(String first, String second) {     
    int maxLen = 0;
    int s1= first.length();
    int s2 = second.length();
    int[][] table = new int[s1+1][s2+1];

    for (int i = 1; i <= s1; i++) {
        for (int j = 1; j <= s2; j++) {
            if (first.charAt(i-1) == second.charAt(j-1)) {
                    table[i][j] = table[i - 1][j - 1] + 1;
                if (table[i][j] > maxLen)
                    maxLen = table[i][j];
            }
        }
    }
    return maxLen;

实施2：

private static String longestCommonSubstring(String S1, String S2)
{
    int Start = 0;
    int Max = 0;
    for (int i = 0; i < S1.length(); i++)
    {
        for (int j = 0; j < S2.length(); j++)
        {
            int x = 0;
            while (S1.charAt(i + x) == S2.charAt(j + x))
            {
                x++;
                if (((i + x) >= S1.length()) || ((j + x) >= S2.length())) break;
            }
            if (x > Max)
            {
                Max = x;
                Start = i;
            }
         }
    }
    return S1.substring(Start, (Start + Max));
}

显示维基百科页面以获取更多信息：https ://en.wikipedia.org/wiki/Longest_common_substring_problem

于 2017-04-26T04:07:14.623 回答