Самая длинная общая подстрока без сокращения слова

Я очень новичок в программировании, и я пытаюсь решить одну из самых длинных распространенных проблем с последовательностями/подстроками в Java. Итак, вопрос алгоритма, над которым я работаю, состоит в том, чтобы найти самую длинную общую подстроку без сокращения слов.

Например: заданные string1 = He had 3 pennies and 5 quarters и string2 = q3nniesp должны возвращать pennies.

Другой пример: string1 = They named the new place face cafe и string2 = e face и вывод будет e face cafe.

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

Я следил за некоторыми из существующих вопросов о стеке и пытался изменить этот код из https://www.geeksforgeeks.org/:

static String findLongestSubsequence(String str1, String str2) {

        char[] A = str1.toCharArray();
        char[] B = str2.toCharArray();
        if (A == null || B == null) return null;

        final int n = A.length;
        final int m = B.length;

        if (n == 0 || m == 0) return null;

        int[][] dp = new int[n+1][m+1];

        // Suppose A = a1a2..an-1an and B = b1b2..bn-1bn
        for (int i = 1; i <= n; i++ ) {
            for (int j = 1; j <= m; j++) {

                // If ends match the LCS(a1a2..an-1an, b1b2..bn-1bn) = LCS(a1a2..an-1, b1b2..bn-1) + 1
                if (A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1] + 1;

                    // If the ends do not match the LCS of a1a2..an-1an and b1b2..bn-1bn is
                    // max( LCS(a1a2..an-1, b1b2..bn-1bn), LCS(a1a2..an-1an, b1b2..bn-1) )
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

            }
        }

        int lcsLen = dp[n][m];
        char[] lcs = new char[lcsLen];
        int index = 0;

        // Backtrack to find a LCS. We search for the cells
        // where we included an element which are those with
        // dp[i][j] != dp[i-1][j] and dp[i][j] != dp[i][j-1])
        int i = n, j = m;
        while (i >= 1 && j >= 1) {

            int v = dp[i][j];

            // The order of these may output different LCSs
            while(i > 1 && dp[i-1][j] == v) i--;
            while(j > 1 && dp[i][j-1] == v) j--;

            // Make sure there is a match before adding
            if (v > 0) lcs[lcsLen - index++ - 1] = A[i-1]; // or B[j-1];

            i--; j--;

        }

        return new String(lcs, 0, lcsLen);
    }

Но я продолжаю получать неправильные результаты. Например, первый вывод дает output = 3nnies, я действительно застрял на этом этапе, может ли кто-нибудь помочь или немного нацарапать алгоритм? Спасибо вам всем.


java algorithm longest-substring
person interstellar    schedule 11.04.2019    source источник
comment
Подстрока: Подстрока — это непрерывная последовательность символов в строке, где порядок имеет значение. Итак, string1 = У него было 3 пенни и 5 четвертаков string2 = q3nniesp Должен вернуть nnies ?   -  person    schedule 11.04.2019
comment
Он должен возвращать копейки. Кажется, он не должен быть непрерывным...   -  person interstellar    schedule 11.04.2019

Ответы (1)


arrow_upward
1
arrow_downward

Я попробовал ваш оригинальный алгоритм, к сожалению, он был не в правильном направлении.

Я исхожу из того, что применяются следующие рекомендации:

  • Соответствующая подстрока содержит символы из данной подстроки, которые могут быть не в порядке.
  • Символ из данной подстроки может появляться несколько раз в совпадающей подстроке.

Поэтому я позволил себе использовать алгоритм грубой силы при использовании java-потоков:

// complexity of O(N*M), where N is the length of the original string and M is the length of the substring
static String longestCommonSequence(String string, String sub) {
    List<Character> primaryMatch = new ArrayList<>();
    List<Character> secondaryMatch = new ArrayList<>();
    // N iterations loop on original string
    for(char c : string.toCharArray()) {
      // M iterations loop on the substring
      if(sub.indexOf(c) != -1) {
        primaryMatch.add(c);
      }
      else {
        if(!primaryMatch.isEmpty()) {
          // replace secondaryMatch content with the current longet match
          if(secondaryMatch.size() <= primaryMatch.size()) {
            secondaryMatch.clear();
            secondaryMatch.addAll(primaryMatch);
          }
          primaryMatch.clear();
        }
      }
    }
    if(primaryMatch.size() < secondaryMatch.size()) {
      return secondaryMatch.stream().map(String::valueOf).collect(Collectors.joining());
    }
    return primaryMatch.stream().map(String::valueOf).collect(Collectors.joining());
}

Выходные данные для предоставленных вами входных данных:

string1 = He had 3 pennies and 5 quarters and string2 = q3nniesp ---> pennies
string1 = They named the new place face cafe and string2 = e face ---> ace face cafe

Обратите внимание на разницу во втором выводе - на основе поведения вывода, которое вы описали, результат вышеприведенного алгоритма является правильным, поскольку ace face cafe длиннее, чем e face cafe, поскольку разрешено многократное использование символов из данной подстроки.

Обратите внимание на тонкую проблему в алгоритме: if(secondaryMatch.size() <= primaryMatch.size())

Текущая реализация, в случае нескольких совпадающих подстрок одинаковой длины, вернет последнее совпадение (на основе порядка символов в исходной строке). Если вы хотите вернуть первое совпадение, замените <= на <.

Если описанные мной предположения не разрешены - прокомментируйте этот ответ, и я обновлю его в соответствии с вашими требованиями.

person Rann Lifshitz    schedule 11.04.2019
comment
это сработало очень хорошо, спасибо за ваше время и внимание. - person interstellar; 16.04.2019
comment
@interstellar: рад помочь, приятель - person Rann Lifshitz; 16.04.2019