алгоритмы поиска Опции

[*оля*]

если даны два списка чисел и нужно найти наибольшую одинаковую последовательность чисел, например, если дано:
1 2 3 4 5 6
1 2 6 2 3 4
то должен вывести 234
подскажите пожалуйста, каким алгоритмом тут лучше воспользоваться?

[*оля*]

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

 
var
a: array [1..10] of integer;
a1: array [1..10] of integer;
k,i,j,i1,j1,kmax: integer;

begin
for i:=1 to 10 do
read(a[i]);
for j:=1 to 10 do
read(a1[j]);
i:=1;
while i<= 10 do begin
  for j:= 1 to 10 do begin
  if a[i]=a1[j] then begin
         i1:=i;
         j1:=j;
         while a[i1]=a1[j1] do begin
         k:=k+1;
         i1:=i1+1;
         j1:=j1+1;
         end;
         if k>kmax then kmax:=k;
         k:=0;
         end;
         end;
  i:=i+1;
  end;
writeln(kmax);
end.

 

.

не подскажете где ошибка? или это вообще неудачная идея так решать данную задачу?

Сообщение отредактировано: *оля* - 16.05.2010 21:02

[volvo]

Это задача о Наибольшей Общей Подпоследовательности. Динамическое программирование.

Как решать - можно посмотреть здесь: Пример №2

[TarasBer]

> не подскажете где ошибка?

Ну, например, что происходит, когда i1 и j1 становятся больше 10? Впрочем,

> это вообще неудачная идея так решать данную задачу

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

Надо делать, как по ссылке. Вот только там нет опечатки?
Вот в этом месте:

Код

if x[i]=y[j] then
    c[i, j]:=c[i-1, j-1] + 1
else
    if c[i-1, j]=c[i, j-1] then
        c[i, j]:=c[i-1, j]
    else
        c[i, j]:=c[i, j-1];

[*оля*]

в другой книге написано в одной строчке по-другому немного:

 else if c[i-1,j] >= c[i,j-1] then ...

а я вообще не могу понять, где что делается(

Добавлено через 5 мин.

Ну, например, что происходит, когда i1 и j1 становятся больше 10?

хм, да, не подумала... а если ввести ограничения, то все равно что-то не то, значит и еще есть ошибки, но я их не вижу

Сообщение отредактировано: *оля* - 18.05.2010 21:36

[TarasBer]

> в другой книге написано в одной строчке по-другому немного:

А вот если там >= вместо =, то это уже ближе к истине.
Правда, время за O(m*n) всё равно странно. Там вроде можно за O(m+n). Или я это путаю с поиском подстроки...

> а если ввести ограничения, то все равно что-то не то

Ну ввёл.

while (i1<=10) and (j1<=10) and (a[i1]=a1[j1]) do begin

У меня всё работает. Надо граничные условия проверять до сравнения элементов. Чтобы в случае выхода за границы элементы не сравнивались. А вообще, этот алгоритм недостоин того, чтобы его отлаживать.

Добавлено через 11 мин.
Хотя не, то, что по ссылке, тоже неверно. Для abc и bac возвращает 2.
А потому, что если длина НОП для ab и ba равна 1 и следующий добавленный элемент и там и там c, то вовсе не значит, что длина НОП для abc и bac равна 2. С чего этому НОПу быть именно в конце у обоих?

[*оля*]

все, в своем не совсем удачном алгоритме нашла еще ошибку, теперь и у меня работает! спасибо за помощь!

алгоритмы, которые я смотрела, считают, что, если заданы строки:
123 и 1523, то наибольшая общая подпоследовательность будет 123 (наверное, это из определения подпоследовательности),
а мне нужно было решить задачу, чтобы выводилось 23.
Поэтому не могу найти алгоритм, который подойдет, а в алгоритме по ссылке что-то разобраться до сих пор не могу, может он тоже ищет подпоследовательность, как в первом случае?(если дано: 123 и 1523, то выдает 123)

[TarasBer]

> Поэтому не могу найти алгоритм, который подойдет, а в алгоритме по ссылке что-то разобраться до сих пор не могу, может он тоже ищет подпоследовательность, как в первом случае?

Выходит, что так.
Всё, теперь я тоже врубился, почему такой результат. Ну да, тут-то надо подпоследовательность подряд идущих элементов, а тот алгоритм ищет и раскиданную подпоследовательность.
Но тут тоже надо подумать над оптимизацией. Пока что есть O(m*n*min(m,n)), короче кубическая сложность.

[*оля*]

Пока что есть O(m*n*min(m,n)), короче кубическая сложность.

мда, надо подумать, как исправить, так оставлять не хочется.

[TarasBer]

А, в википедии же есть аналогичный алгоритм, но как раз для подстрок, а не подпоследовательностей, ровно то, что тут надо: http://ru.wikipedia.org/wiki/Наибольшая_общая_подстрока

[TarasBer]

http://e-maxx.ru/algo/suffix_automata

Тут уже за o(m+n)
Я проверил, слово в слово переписал сишный алгоритм на паскаль, вроде работает.
Впрочем, вряд ли вам задавали суффиксные автоматы, это уже дебри пошли.

[*оля*]

Спасибочки большое!!!)))
ну да, это уже все сложно, но ради интереса попробую разобраться)))

[Lapp]

это уже все сложно, но ради интереса попробую разобраться)))

Ты обязательно попробуй, но сначала я бы советовал разобраться с тем, что ты сама сделала )). Можно дать несколько советов?

Посмотри - это твой код, немного улучшенный:

const
  n=10;
var
  a,b: array [1..n] of integer;
  i,j,k,kmax: integer;

begin
  for i:=1 to n do read(a[i]);
  for j:=1 to n do read(b[j]);
  kmax:=0;
  for i:=1 to n do
    for j:= 1 to n do begin
      k:=0;
      while a[i+k]=b[j+k] do Inc(k);
      if k>kmax then kmax:=k
    end;
  writeln(kmax)
end.

Далее, в порядке "прихода в голову", а не в порядке важности:

1. Всегда старайся избегать явного указания чисел в программе, заводи константы (у меня - n).

2. Почему у тебя по i цикл while, а по j - for?

3. ВСЕ переменные перед использованием должны быть инициированы (у тебя не инициированы k и kmax).

4. Твои if и while внутри цикла выполняют выполняют одну и ту же функцию - объедини их )).

5. Избегай лишних переменных.

6. Не нужно дважды объявлять один тип там, где это _не_нужно_. Формально твои а и а1 принадлежат к разным типам. Тут это не важно, но в принципе может вызвать проблемы.

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

А вообще - +1 за то, что сама решаешь )).

[*оля*]

Можно дать несколько советов?

Буду только благодарна!))

Посмотри - это твой код, немного улучшенный:

 while a[i+k]=b[j+k] do Inc(k);
 

.
не утверждаю, но возможно, тут не хватает еще одного условия?
За алгоритм спасибо, он гораздо лучше моего)


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

Тут было написано для двух массивов, а в задаче 2 динамических списка. Можно ли данный алгоритм преобразовать к этой задаче или проще 2 списка изначально заменить двумя динамическими массивами?

А вообще - +1 за то, что сама решаешь )).

спасибо)

Сообщение отредактировано: *оля* - 22.05.2010 15:39

[*оля*]

что-то совсем у меня со списками ничего не получается, пыталась изменить ваш алгоритм под свою задачу, но не выходит пока(

 type
	TWordStr = integer;
	PTItem = ^TItem;
	TItem = record
	            Data: TWordStr;
	            next: PTItem;
	end;
	TWordList = record
	first, last, head: PTItem;
	end;
var
kmax,k: integer;
L,L1: TWordList;
p, p1: PTItem;

...
begin
...
p:=L.first;
p1:=L1.first;
while p<>nil do begin
  while p1<>nil do begin
  k:=0;
    while (p<> nil) and (p1<>nil) and (p^.Data = p1^.Data) do
      begin
      k:=k+1;
      p:=p^.next;     
      p1:=p1^.next; 
      end;
      if k>kmax then kmax:=k;
      end;
      end;
    p:=p^.next;  //до этого значение уже было изменено, и теперь тут не то, что нужно
    p1:=p1^.next; //а как исправить?
    end;
     writeln(kmax);
end. 

не могли бы вы помочь разобраться?

[volvo]

до этого значение уже было изменено, и теперь тут не то, что нужно

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

  p := L.first;
  while p <> nil do
  begin

    p1 := L1.first; { <--- Это по поводу начала внутреннего цикла }
    while p1 <> nil do
    begin
      k := 0;
      pp := p; pp1 := p1; { А это - доп. переменные }
      while (pp <> nil) and (pp1 <> nil) and (pp^.Data = pp1^.Data) do
      begin
        inc(k);
        pp := pp^.next;
        pp1 := pp1^.next;
      end;

      if k > kmax then kmax := k;

      p1 := p1^.next; { продолжаем внутренний цикл }
    end;

    p := p^.next; { Продолжаем цикл внешний }
  end;
  writeln(kmax);

[*оля*]

Спасибо большое!!! теперь все стало гораздно понятнее))

[*оля*]

  p := L.first;
  while p <> nil do
  begin

    p1 := L1.first; { <--- Это по поводу начала внутреннего цикла } 
    while p1 <> nil do
    begin
      k := 0;
      pp := p; pp1 := p1; { А это - доп. переменные }
      while (pp <> nil) and (pp1 <> nil) and (pp^.Data = pp1^.Data) do
      begin
        inc(k);
        pp := pp^.next;
        pp1 := pp1^.next;
      end;

      if k > kmax then kmax := k;

      p1 := p1^.next; { продолжаем внутренний цикл }
    end;

    p := p^.next; { Продолжаем цикл внешний }
  end;
  writeln(kmax);

А если после того, как нашли эту подстроку, нужно ее удалить, то как это сделать можно? Знаю, как удалить один элемент, а вот как удалить подстроку из списка не понимаю (
Подскажите пожалуйста как поступить, заранее спасибо!)

[volvo]

*оля*, тут возможны 2 варианта...

Первый (я буду удалять подпоследовательность из ПЕРВОГО списка, а не из второго):

{ Чуть-чуть изменяем цикл поиска (нам понадобится еще одна переменная)}
      if k > kmax then 
      begin
        kmax := k; p_del := p; { <--- Запоминаем, откуда начиналась самая длинная послед-ть }
      end;

  { И после окончания циклов: }
  p := p_del; { Запоминаем, где начиналась последовательность. Оно чуть ниже пригодится }

  { Удаляем обычным способом kmax элементов, начиная с запомненного }
  for i := 1 to kmax do
  begin
    pp := p_del;
    p_del := p_del^.next;
    dispose(pp);
  end;

  {
    А теперь проверяем, не равен ли L.first тому, запомненному адресу начала 
    последовательности. Если равен - значит наибольшая последовательность
    была в самом начале списка, тогда все очень просто: началом списка будем
    считать p_del, он теперь содержит адрес элемента, следующего за последним
    удаленным...

    А вот если последовательность начиналась не с начала списка - то чуть
    сложнее, надо найти тот элемент, который _указывает_ на место, где раньше
    была последовательность... То есть, тот, что находился ПЕРЕД ней. Найдем
    его, и его NEXT поменяем на p_del...
  }
  if L.first = p then L.first := p_del
  else begin
    pp := L.first;
    while pp^.next <> p do pp := pp^.next;
    pp^.next := p_del;
  end;

Это все, можно теперь печатать список, найденая последовательность из него уже удалена...

Это был первый способ. Второй похож, но немного отличается - не удалять элементы один за одним в цикле, а просто пропускать их (переходить к следующему). Как только дошли до конца нашей последовательности, "обрубаем" список NIL-ом и чуть-чуть подправляем указатели так, чтобы "вырезанный" кусок был отдельно, а то, что было ПЕРЕД и ПОСЛЕ него - склеиваем в одно. Это не так сложно, как кажется, достаточно нарисовать на бумажке список и посмотреть, куда какие связи надо установить...

Если у тебя уже есть подпрограмма, удаляющая список, то я бы все-таки попробовал реализовать именно второй метод на твоем месте, потому что удалять тот, "вырезанный" кусок можно с помощью готовой подпрограммы (это ведь самостоятельный список, у нас есть адрес его начала, он заканчивается пустым указателем, как положено), а это всегда лучше, не будет дублирования кода... Вот у меня сейчас подпоследовательность удаляется в одном месте, а сами списки я буду удалять в другом, это приведет к копированию куска кода.

Так что все-таки попробуй реализовать второй вариант, если что не получится - говори, подскажем

[*оля*]

volvo, вы как всегда меня спасаете, спасибо большое!!!!

с первым вариантом разобралась,потом сделала так, чтобы удалялась последовательность из двух списков, а вот со вторым вариантом посложнее)

сейчас хочу сделать цикл:

repeat 

- найти длину наибольшей общей подстроки;
-удалить найденную подстроку из списков;
- сложить все найденные длины наибольших общих подстрок;
(в общем все то, что вы мне уже помогли реализовать)

until kmax<=10;  <--- но здесь наверняка не хватает  чего-то? или вообще так нельзя будет организовать цикл?

если так и писать цикл, то делает один раз только все.
И нужно ли писать в конце "пока kmax<=10 или количество компонентов списка1 или списка2 равно 0"? я запуталась, помогите пожалуйста)

Сообщение отредактировано: *оля* - 24.05.2010 19:56