Застрял в поиске самого глубокого пути в общем обходе дерева, пытаясь найти самую большую общую подстроку

Одна проблема, которую я здесь вижу, заключается в том, что глубина узла в дереве суффиксов не совпадает с длиной строки на этом пути. Каждое ребро в суффиксном дереве аннотируется диапазоном символов, поэтому строка, закодированная серией узлов глубины пять, может иметь меньшую длину, чем строка, закодированная глубиной два. Вам, вероятно, потребуется настроить свой алгоритм, чтобы справиться с этим, отслеживая эффективную длину строки, которую вы создали до сих пор, а не количество узлов в пути, который вы проследили до этого момента.

Вторая проблема, которую я только что заметил, заключается в том, что у вас, похоже, есть только одна переменная current, которая используется во всех разных ветвях рекурсии. Вероятно, это портит ваше состояние при рекурсивных вызовах. Например, предположим, что вы находитесь в узле и имеете путь длины три, и что есть два потомка, первый из которых заканчивается только суффиксом первой строки, а второй заканчивается суффиксом обе струны. В этом случае, если вы сделаете рекурсивный вызов первой строки, вы в конечном итоге выполните строку

current = new ArrayList<SuffixNode>();  

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

Чтобы исправить это, я предлагаю сделать current параметром функции, а затем при необходимости создать новый ArrayList, а не стирать существующий ArrayList. Некоторая другая логика, возможно, также должна измениться, чтобы учесть это.

Учитывая это, я бы предложил написать функцию в псевдокоде следующим образом (поскольку я не знаю подробностей реализации вашего дерева суффиксов):

• Если текущий узел нулевой, вернуть 0.
• Если текущий узел не получен из обеих строк, вернуть 0.
• Otherwise:
  • Set maxLen = 0.
  • For each child node:
    • Compute the length of the longest common substring rooted at that node.
    • Добавьте к этой длине количество символов вдоль края до этого дочернего элемента.
    • Обновите maxLen, если оно превышает старое значение.
  • Вернуть макслен.

Надеюсь это поможет!

Хотя это и не ответ, я бы решил это, используя стандартные коллекции с поиском O (n log n).

static String findLongestCommonSubstring(String s1, String s2) {
    if (s1.length() > s2.length()) return findLongestCommonSubstring(s2, s1);

    NavigableSet<String> substrings = new TreeSet<>();
    for (int i = 0; i < s1.length(); i++)
        substrings.add(s1.substring(i));
    String longest = "";
    for (int i = 0; i < s2.length(); i++) {
        String sub2 = s2.substring(i);
        String floor = match(substrings.floor(sub2), sub2);
        String ceiling = match(substrings.ceiling(sub2), sub2);
        if (floor.length() > longest.length())
            longest = floor;
        if (ceiling.length() > longest.length())
            longest = ceiling;
    }
    return longest;
}

private static String match(String s1, String s2) {
    if (s1 == null || s2 == null) return "";
    for (int i = 0; i < s1.length() && i < s2.length(); i++)
        if (s1.charAt(i) != s2.charAt(i))
            return s1.substring(0, i);
    return s1.substring(0, Math.min(s1.length(), s2.length()));
}

public static void main(String... args) {
    System.out.println(findLongestCommonSubstring("sdlkjfsdkljfkljsdlfkjaeakjf", "kjashdkasjdlkjasdlfkjaesdlk"));
}

отпечатки

sdlfkjae

Вы ДОЛЖНЫ идти по пути суффиксного дерева? Если нет, то почему вы не могли:

public String findCommonSubString(string str1, string str2) {
   string mainStr;
   string otherStr;
   string commonStr = "";
   string foundCommonStr = "";
   boolean strGrowing = false;

   If (str1.length() > str2.length()) {
      mainStr = str1;
      otherStr = str2;
   } else {
      mainStr = str2;
      otherStr = str1;
   }

   int strCount = 0;

   for(int x = 0; x < mainStr.length();x++) {
      strCount = 1;
      strGrowing = true;

      while(strGrowing) {
         if (otherStr.IndexOf(mainStr.substring(x, strCount) >= 0) {
            //Found a match now add a character to it.
            strCount++;

            foundCommonStr = mainStr.substring(x, strCount);

            if (foundCommonStr.length() > commonStr.length()) {
               commonStr = foundCommonStr;
            }
         } else {
            strGrowing = false;
         }
      }

   }

return commonStr;

}

Я не запускал это ... но я буду. По сути, это начнется с наименьшей из двух строк и попытается найти общую строку между двумя строками, используя IndexOf и подстроку. затем, если это произойдет, он снова проверит, но на этот раз проверит, добавив еще один символ из меньшей строки к проверке. Он сохранит строку в переменной commonStr только в том случае, если найденная строка (foundCommonStr) больше, чем commonStr. Если он не находит совпадения, то он уже сохранил наибольшую общую строку для возврата.

Я считаю, что идея верна, но я не запускал ее в компиляторе.