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

[*оля*]

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

[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-ом и чуть-чуть подправляем указатели так, чтобы "вырезанный" кусок был отдельно, а то, что было ПЕРЕД и ПОСЛЕ него - склеиваем в одно. Это не так сложно, как кажется, достаточно нарисовать на бумажке список и посмотреть, куда какие связи надо установить...

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

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