Поиск всех общих подстрок заданных двух строк

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

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

Например, с учетом входных строк eatsleepnightxyz и eatsleepabcxyz, результаты должны быть:

• eatsleep (из-за eatsleepnightxyz eatsleepabcxyz)
• xyz (из-за eatsleepnightxyz eatsleepabcxyz)
• a (из-за eatsleepnightxyz eatsleepabcxyz)
• t (из-за eatsleepnightxyz eatsleepabcxyz)

Однако набор результатов не должен включать e из eatsleepnightxyz eatsleepabcxyz, поскольку оба e уже содержатся в упомянутом выше eatsleep. Вы также не должны включать ea, eat, ats и т.д., Так как все они покрываются eatsleep.

В этом случае вам не нужно использовать методы командной строки String, такие как: contains, indexOf, StringTokenizer, split и replace.

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

 For String S1:
     Find all the substrings of S1 of all the lengths
     While doing so: Check if it is also a substring of 
     S2.

Попытка выяснить временную сложность моего подхода.

Пусть две заданные строки: n1-String и n2-String

• Число подстрок S1, очевидно, равно n1 (n1 + 1)/2.
• Но нам нужно найти среднюю длину подстроки S1.
• Допустим, что это m. Хорошо найти m отдельно.
• Сложность времени для проверки того, является ли m-String подстрокой n-String - O (n * m).
• Теперь мы проверяем, что каждая m-String является подстрокой S2, который является n2-String.
• Это, как мы видели выше, является алгоритмом O (n ² m).
• Время, требуемое общим алгоритмом, тогда
• Tn = (количество подстрок в S1) * (средняя длина подстроки для процедуры сравнения символов)
• Выполняя определенные вычисления, я пришел к выводу, что временная сложность O (n ³ m ²)
• Теперь наша задача - найти m в терминах n1.

Попытка найти m в терминах n1.

T _n= (n) (1) + (n-1) (2) + (n-2) (3) +..... + (2) (n- 1) + (1) (n)
где T _n - сумма длин всех подстрок.

Среднее будет деление этой суммы на общее количество созданных подстрок.

Это просто задача суммирования и деления, решение которой выглядит следующим образом: O (n)

Поэтому...

Время работы моего алгоритма O (n ^ 5).

С учетом этого я написал следующий код:

 package pack.common.substrings;

 import java.util.ArrayList;
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Set;

 public class FindCommon2 {
    public static final Set<String> commonSubstrings = new      LinkedHashSet<String>();

 public static void main(String[] args) {
    printCommonSubstrings("neerajisgreat", "neerajisnotgreat");
    System.out.println(commonSubstrings);
}

 public static void printCommonSubstrings(String s1, String s2) {
    for (int i = 0; i < s1.length();) {
        List<String> list = new ArrayList<String>();
        for (int j = i; j < s1.length(); j++) {
            String subStr = s1.substring(i, j + 1);
            if (isSubstring(subStr, s2)) {
                list.add(subStr);
            }
        }
        if (!list.isEmpty()) {
            String s = list.get(list.size() - 1);
            commonSubstrings.add(s);
            i += s.length();
        }
    }
 }

 public static boolean isSubstring(String s1, String s2) {
    boolean isSubstring = true;
    int strLen = s2.length();
    int strToCheckLen = s1.length();
    if (strToCheckLen > strLen) {
        isSubstring = false;
    } else {
        for (int i = 0; i <= (strLen - strToCheckLen); i++) {
            int index = i;
            int startingIndex = i;
            for (int j = 0; j < strToCheckLen; j++) {
                if (!(s1.charAt(j) == s2.charAt(index))) {
                    break;
                } else {
                    index++;
                }
            }
            if ((index - startingIndex) < strToCheckLen) {
                isSubstring = false;
            } else {
                isSubstring = true;
                break;
            }
        }
    }
    return isSubstring;
 }
}

Объяснение для моего кода:

 printCommonSubstrings: Finds all the substrings of S1 and 
                        checks if it is also a substring of 
                        S2.
 isSubstring : As the name suggests, it checks if the given string 
               is a substring of the other string.

Проблема: с учетом входных данных

  S1 = "neerajisgreat";
  S2 = "neerajisnotgreat"
  S3 = "rajeatneerajisnotgreat"

В случае S1 и S2 выход должен быть: neerajis и great но в случае S1 и S3 выход должен был быть: neerajis, raj, great, eat, но все же я получаю neerajis и great как вывод. Мне нужно понять это.

Как мне создать код?

Ответы

public static Set<String> longestCommonSubstrings(String s, String t) {
    int[][] table = new int[s.length()][t.length()];
    int longest = 0;
    Set<String> result = new HashSet<>();

    for (int i = 0; i < s.length(); i++) {
        for (int j = 0; j < t.length(); j++) {
            if (s.charAt(i) != t.charAt(j)) {
                continue;
            }

            table[i][j] = (i == 0 || j == 0) ? 1
                                             : 1 + table[i - 1][j - 1];
            if (table[i][j] > longest) {
                longest = table[i][j];
                result.clear();
            }
            if (table[i][j] == longest) {
                result.add(s.substring(i - longest + 1, i + 1));
            }
        }
    }
    return result;
}

  e a t s l e e p a b c x y z
e 1 0 0 0 0 1 1 0 0 0 0 0 0 0
a 0 2 0 0 0 0 0 0 1 0 0 0 0 0
t 0 0 3 0 0 0 0 0 0 0 0 0 0 0
s 0 0 0 4 0 0 0 0 0 0 0 0 0 0
l 0 0 0 0 5 0 0 0 0 0 0 0 0 0
e 1 0 0 0 0 6 1 0 0 0 0 0 0 0
e 1 0 0 0 0 1 7 0 0 0 0 0 0 0
p 0 0 0 0 0 0 0 8 0 0 0 0 0 0
n 0 0 0 0 0 0 0 0 0 0 0 0 0 0
i 0 0 0 0 0 0 0 0 0 0 0 0 0 0
g 0 0 0 0 0 0 0 0 0 0 0 0 0 0
h 0 0 0 0 0 0 0 0 0 0 0 0 0 0
t 0 0 1 0 0 0 0 0 0 0 0 0 0 0
x 0 0 0 0 0 0 0 0 0 0 0 1 0 0
y 0 0 0 0 0 0 0 0 0 0 0 0 2 0
z 0 0 0 0 0 0 0 0 0 0 0 0 0 3