Нахождение самой длинной общей подстроки с начальными индексами

Question

Я видел эту реализацию кода здесь . Он в основном принимает две строки, находит самую длинную общую подстроку и возвращает ее длину. Я хотел немного изменить его, чтобы получить начальные индексы подстрок для каждого слова, но просто не могу понять. Я знаю, что это должно быть возможно, так как мы работаем с индексами строки. Я напишу свою отредактированную версию кода ниже:

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 вместо создания другого массива index, как в решении 1.

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 пустым после выполнения второго l oop каждый раз, из-за которого, если символы не совпадают при следующем запуске, соответствующий индекс 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 и добавьте 1 к обоим значениям i и j, которые будут учитывать разницу между тем, что вы ожидали, и тем, что вы получили.

Вот код на всякий случай:

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

return ans;

Мой ответ может быть не таким исчерпывающим, как у Прерны Гупты, но, с другой стороны, он сохраняет ваш алгоритм таким же, каким он является сейчас, поэтому я буду оставьте это здесь на всякий случай.