Сравнить несколько подстрок

Question

Я пытаюсь написать базовый секвенсор ДНК.При этом, учитывая две последовательности одинаковой длины, он выведет одинаковые строки с минимальной длиной 3. Таким образом, ввод

abcdef dfeabc

вернет

1 abc

Я не уверен, как решить проблему.Я могу сравнить две строки и посмотреть, полностью ли они совпадают.Оттуда я могу сравнить размер строки длины-1, т.е. если dfeabc содержит abcde.Тем не менее, как я могу заставить программу делать все возможные строки, вплоть до минимального размера 3 символа?Одна проблема связана с приведенным выше примером длины 1, мне также нужно будет выполнить строку bcdef и сравнить ее.

Answer 1

Наивным способом было бы получить каждую подстроку строки A и посмотреть, находится ли она в строке B.

Вот наивный способ сделать это:

for ( int i = 0; i < a.length; i++ ) {
   for ( int j = i+1; j <= a.length; j++ ) {
       if (b.contains(a.substring(i, j))) {
           //if longer than last found match, record this match
       }
   }
}

Чуть болееоптимальным способом было бы сначала посмотреть на более длинные подстроки, чтобы первая подходящая подстрока была обязательно самой длинной.

for ( int length = a.length; length > 0; length-- ) {
     for ( int i = 0; i + length < a.length; i++ ) {
         if ( b.contains(a.substring(i, i+length)) ) {
             //this is the biggest match
         }
     }
}

Answer 2

Вам необходимо использовать алгоритм Longest Common Substring, проблему динамического программирования.Проверьте запись Википедии для объяснения алгоритма и здесь для примера реализации.

Answer 3

Если вы хотите решить это простым способом, не используя Java API для поиска, вы можете думать об этом так: для каждой пары возможных начальных индексов i в первой строке и j во второй строке вперед в обоих случаях, когда соответствующие символы в первой и второй строке равны, и возвращают результат, если вы выполнили хотя бы 3 шага.