搜索代码中的索引问题

Question

我编写了以下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。有什么帮助吗？

谢谢

Answer 1

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

实施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

Answer 2

我认为有两个地方出了问题。

--其中一个问题是

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

正如M2E67在他的第二个实现中所展示的，您需要检查i是否越界，如果是，则跳过比较。举个例子:对于您的第一组字符串，当i = cad1.length-1和j = cad2.length-2时，它将向i添加一个，生成i = cad1.length，并在for循环的下一次迭代中执行cad1.charAt(i) --这将抛出一个ArrayIndexOutOfBounds异常。

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

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

Answer 3

方法longestEqualSubstring使用两个字符串来查找最长相等的sustring。它提取s1的1个字符，并将其与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