查找具有起始索引的最长公共子串

Question

我看到了这个代码实现here。它基本上需要两个字符串，找到最长的公共子字符串，以及 returns 它的长度。我想稍微修改它以获得每个单词的子字符串的起始索引，但就是想不通。我知道这应该是可能的，因为我们正在处理字符串的索引。我将编写以下代码的编辑版本：


public class Main {
    public class Answer {
        int i, j, len;
        Answer(int i, int j, int len) {
            this.i = i;
            this.j = j;
            this.len = len;
        }
    }
    public Answer find(String s1,String s2){

        int n = s1.length();
        int m = s2.length();

        Answer ans = new Answer(0, 0, 0);
        int[] a = new int[m];
        int b[] = new int[m];

        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(s1.charAt(i)==s2.charAt(j)){
                   if(i==0 || j==0 )a[j] = 1;
                   else{
                       a[j] = b[j-1] + 1;
                   }
                   ans.len = Math.max(ans.len, a[j]);
                   ans.i = i;
                   ans.j = j;
                }

            }
            int[] c = a;
            a = b;
            b = c;
        }
        return ans;
    }
}

Answer 1

我假设这是两个字符串： s1 = "abcdxyz" s2 = "xyzabcd" 然后因为 abcd 是最长的公共子串所以你需要在 s1 和 s2 中这个子串的索引分别是 0,3.

有两种解决方法：

解决方案 1：

在这里，我创建了一个 index 数组，我在其中存储字符串的起始索引，索引数组的索引 0 用于存储 s1，索引 1 用于存储 s2。

public Answer  find(String s1,String s2){

    int n = s1.length();
    int m = s2.length();

    Answer ans = new Answer(0, 0, 0);
    int[] a = new int[m];
    int b[] = new int[m];
    int indexes[] = new int[2];
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(s1.charAt(i)==s2.charAt(j)){
               if(i==0 || j==0 )a[j] = 1;
               else{
                   a[j] = b[j-1] + 1;
               }
               if(a[j]>ans.len) {
                   ans.len = a[j];
                   indexes[0]=(i+1) - ans.len;
                   indexes[1]=(j+1) - ans.len;
               }
               ans.i = i;
               ans.j = j;

            }

        }
        int[] c = a;
        a = b;
        b = c;
    }
    return ans;
}

解决方案 2：

我不确定你的 Answer 对象 i 和 j 值在做什么，但我们可以让它们也存储这些值，i 存储 s1 字符串和 j 存储对于 s2 字符串，而不是像解决方案 1 中那样创建不同的 index 数组。

public Answer  find(String s1,String s2){

    int n = s1.length();
    int m = s2.length();

    Answer ans = new Answer(0, 0, 0);
    int[] a = new int[m];
    int b[] = new int[m];
    int indexes[] = new int[2];
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(s1.charAt(i)==s2.charAt(j)){
               if(i==0 || j==0 )a[j] = 1;
               else{
                   a[j] = b[j-1] + 1;
               }
               if(a[j]>ans.len) {
                   ans.len = a[j];
                   ans.i=(i+1) - ans.len;
                   ans.j=(j+1) - ans.len;
               }

            }

        }
        int[] c = a;
        a = b;
        b = c;
    }
    return ans;
}

目前这还不能正确计算 LCS。问题是你没有在每次运行第二次循环后将数组 a 设为空，因为如果字符在下一个运行对应的 a 存储索引中不匹配仅以前的值，但应为 0。

更新代码为：

 public Answer  find(String s1,String s2){

            int n = s1.length();
            int m = s2.length();

            Answer ans = new Answer(0, 0, 0);
            int[] a;
            int b[] = new int[m];
            int indexes[] = new int[2];
            for(int i = 0;i<n;i++){
                a = new int[m];
                for(int j = 0;j<m;j++){
                    if(s1.charAt(i)==s2.charAt(j)){
                       if(i==0 || j==0 )a[j] = 1;
                       else{
                           a[j] = b[j-1] + 1;
                       }
                       if(a[j]>ans.len) {
                           ans.len = a[j];
                           ans.i=(i+1) - ans.len;
                           ans.j=(j+1) - ans.len;
                       }

                    }

                }
                b = a;
            }
            return ans;
        }

Answer 2

这可能不是您正在寻找的答案，但是它确实解决了你的问题，只需要额外的两行。

在返回答案之前，只需减去 LCS 的长度并将 i 和 j 都加 1，这将说明您的预期与实际结果之间的差异。

以下是以防万一的代码：

ans.i = ans.i - ans.len + 1;
ans.j = ans.j - ans.len + 1;

return ans;

我的回答可能不像 Prerna Gupta 的回答那么全面，但另一方面，它确实使您的算法保持原样，所以我将其保留在这里以防万一。

查找具有起始索引的最长公共子串

Finding Longest Common Substring with starting indexes

java

algorithm

lcs

解决方案 1：

解决方案 2：