Подход к самой длинной общей подстроке

Question

Подход к самой длинной общей подстроке

В задаче программирования в Общий ребенок , я выбрал иной подход, чем общая проблема Longest Common Substring. Кодекс

#include <cmath>
#include <cstdio>
#include <vector>
#include<string>
#include <iostream>
#include <algorithm>
using namespace std;

void max(string a,string b,int n)
{
int count=0,x=-1,prev=0,i,j,k;
for(i=0;i<n;i++)
{
x=-1;
for(j=i;j<n;j++)
{
for(k=x+1;k<n;k++)
{
if(a[j]==b[k])
{
count++;
x=k;
break;
}
}
}
if(prev<count)
{
prev=count;
}
count=0;
}
cout<<prev;
}

int main() {
string a,b;
int n;
cin>>a;
cin>>b;
n=a.length();
max(a,b,n);
return 0;

Принимая меньшие TestCases я могу получить решение, но я не могу получить решение для более длинных.

Что я сделал, так это

Ввод: ABCDEF — Пусть это будет FBDAMN — Пусть это будет b, как это вставлено в
код. Выход: 2. т.е. для BD является подстрокой.

Итак, что я делаю здесь — проверяю подходящую подстроку для каждого
подстрока, и выведите наибольшее. то есть. подстрока для ABCDEF,
BCDEF, CDEF, DEF, EF, F, который обозначает самый внешний цикл здесь (цикл i)

Теперь второй цикл соответствует каждой букве в строке т.е. это повторяется
для (1 … n), (2 … n), (3 … n), …, (n), то есть начинается с буквы
я уточняю.

Теперь третий цикл перебирает всю строку B, чтобы увидеть,
a [j] соответствует любой букве в B, если да, то счетчик увеличивается.

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

Пробный прогон будет как для примера (массивы от 0 до n-1)

a = abcdef b = fbdamn

когда я = 0 — вся строка соответствует abcdef

x = -1, так что k повторяется от 0 до n-1. Итак, a = f? а = Ь? а = д? а = а? считать =
кол + 1; поэтому х устанавливается как 3 (позиция а). элементы после A в банке
только после A в B, так что х = 3. следовательно, k повторяется от 4 до 5 b = m?
б = п? с = м? с = п? …. … …

Теперь мы сохраняем значение предыдущего подсчета, если оно больше, чем рассчитывает
до. поэтому maxcount = count, а затем сбросить счетчик до 0 и сбросить
положение х = -1.

i = 1 т.е. строка = BCDEF k от 0 до n Итак, B = F? B = B? count = count + 1 //
становится 1 х устанавливается как 1 (положение B) k от 2 до n c = d? с = а? с = т? с = п?
k от 2 до n d = d? count = count + 1 // становится 2 x устанавливается как 2 k из 3
п е = а? е = м? е = п? k от 3 до n f = a? f = m? f = n? тогда, если максимальное количество (пред. в
код) больше текущего счетчика, затем maxcount = счетчик, сброс счетчика =
0, х = -1; тогда это идет так для CDEF, DEF, EF, F максимальная подстрока
здесь становится таким 2

Работает для коротких тестов, но не для длинных.

Тестовые случаи, для которых это работает:

OUDFRMYMAW AWHYFCCMQX

С выходом 2

Не работает для

WEWOUCUIDGCGTRMEZEPXZFEJWISRSBBSYXAYDFEJJDLEBVHHKS FDAGCXGKCTKWNECHMRXZWMLRYUCOCZHJRRJBOAJOQJZZVUYXIC

С правильным выводом 15 и мой вывод 10. Может ли кто-нибудь объяснить мне, где я делаю ошибку в

2

algorithm c++lcs longest-substring string

Решение

Другие решения

Одна проблема, которую я предвижу, заключается в следующем:

Если a = ABCDEFG и b = ACDEFGB,

Теперь он сначала будет соответствовать A, затем — B, но тогда k станет уже 6. Следовательно, дальнейшие буквы CDEFG не будут совпадать.

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

Ваш код должен возвращать максимально общего ребенка как CDEFG.

РЕДАКТИРОВАТЬ: Это не самая длинная проблема общих подстрок, но самая длинная проблема общих подпоследовательностей. http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

6

import java.util.Scanner;
public class JavaApplication8 {
public static int find(String s1,String s2){
int n = s1.length();
int m = s2.length();
int ans = 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 = Math.max(ans, a[j]);
}

}
int[] c = a;
a = b;
b = c;
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s1 = sc.next();
String s2 = sc.next();
System.out.println(find(s1,s2));
}

}

Time Complexity O(N).
Space Complexity O(N).

0

Источник

Accepted Answer

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

A = "abcd"B = "acdb"

Ваш алгоритм возвращает 2 потому что это средства "ab"в то время как самая длинная подпоследовательность "acd"длиной 3.

Эти две строки тщательно созданы, чтобы обмануть ваш алгоритм и привести к неверному результату. Ваш алгоритм будет соответствовать 'a's в начальной позиции, перейти ко второму символу 'b' строки Aи сопоставьте его в последней позиции строки B, На данный момент ваш алгоритм обречен: он не найдет 'c' а также 'd', потому что все персонажи B исчерпаны. То, что он должен был сделать, это сделать так, как будто он может добиться большего успеха, откатив решение о совпадении 'b', Ответом на это является громкое «да»: если мы пропустим второй символ Aмы бы соответствовали обоим 'c' а также 'd', для правильного результата 3.

Правильная реализация LCS (с DP или с мемоизацией) делает этот возврат без увеличения времени экспоненциально. Это один из простейших алгоритмов DP для изучения и реализации, поэтому у вас не должно возникнуть проблем с его применением для решения поставленной задачи.

4