Подход к самой длинной общей подстроке
В "Задаче программирования на общего ребенка" я использовал иной подход, чем общая проблема "Самая длинная общая подстрока". Кодекс
#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 является подстрокой.
Итак, что я делаю здесь - проверяю подходящую подстроку для каждой подстроки a и печатаю наибольшую. то есть. подстрока для ABCDEF, BCDEF,CDEF,DEF,EF,F, которая обозначает самый внешний цикл здесь (цикл i)
Теперь второй цикл соответствует каждой букве в строке т.е. он выполняет итерации для (1...n),(2...n),(3...n),...,(n), то есть начинается с указанной мной буквы.
Теперь третий цикл перебирает всю строку B, чтобы увидеть, совпадает ли a[j] с какой-либо буквой в B, если да, то счетчик увеличивается.
Поскольку мы можем только удалять буквы из подстроки и не перемешивать ее, т.е. каждая буква должна иметь одинаковый относительный порядок в обеих строках, я ищу B после того, как предыдущая буква была найдена, с использованием x.
Пробный прогон будет как для примера (массивы от 0 до n-1)
a = abcdef b = fbdamn
когда я =0 - вся строка соответствует abcdef
x = -1, так что k повторяется от 0 до n-1. Итак, a = f? а = Ь? а = д? а = а? количество = количество +1; поэтому х устанавливается как 3(позиция а). элементы после a в A могут встречаться только после a в B, поэтому x=3. следовательно, k повторяется от 4 до 5 b=m? б = п? с = м? с = п?..........
Теперь мы сохраняем значение предыдущего счетчика, если оно больше, чем счетчик ранее. поэтому maxcount=count, а затем сбросить счетчик до 0 и сбросить позицию x = -1.
i = 1, т.е. строка = BCDEF k от 0 до n Итак, B=F? B = B? count=count+1 // становится 1 x устанавливается как 1(позиция B) k от 2 до nc = d? с = а? с = т? с = п? k от 2 до n d=d? count = count+1 // становится 2 x устанавливается как 2 k от 3 до n e=a?e=m?e=n? k от 3 до nf = a? f = m? f = n? затем, если максимальное количество (пред. в коде) больше текущего значения, тогда maxcount = количество, сброс счетчика = 0, x=-1; тогда это идет так для CDEF, DEF, EF, F, максимальная подстрока здесь становится таким образом 2
Работает для коротких тестов, но не для длинных.
Тестовые случаи, для которых это работает:
OUDFRMYMAW AWHYFCCMQX
С выходом 2
Не работает для
WEWOUCUIDGCGTRMEZEPXZFEJWISRSBBSYXAYDFEJJDLEBVHHKS FDAGCXGKCTKWNECHMRXZWMLRYUCOCZHJRRJBOAJOQJZZVUYXIC
С правильным выводом 15 и моим выводом 10. Может ли кто-нибудь объяснить мне, где я делаю ошибку в
3 ответа
Проблема в том, что в вашем алгоритме используется наивный жадный подход: он делает совпадение, как только его видит, и никогда не пересматривает свое решение после этого, пока не доберется до следующей подстроки. Контрпримером можно продемонстрировать, что эта жадная стратегия не работает для 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 для изучения и реализации, поэтому у вас не должно возникнуть проблем с его применением для решения поставленной задачи.
Одна проблема, которую я предвижу, заключается в следующем:
Если a = ABCDEFG и b = ACDEFGB,
Теперь он сначала будет соответствовать A, затем - B, но тогда k станет уже 6. Следовательно, дальнейшие буквы CDEFG не будут совпадать.
Следовательно, возможная строка ACDEFG должна быть пропущена.
Ваш код должен возвращать максимально общего ребенка как CDEFG.
РЕДАКТИРОВАТЬ: Это не самая длинная общая проблема подстрок, но самая длинная общая проблема подпоследовательности. http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/
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).