Наибольшая общая возрастающая последовательность

#cpp #c #алгоритм

Имеется задача. Найти наибольшую общую возрастающую последовательность среди двух
последовательностей длинной n и m. Я написал алгоритм за O(n^2), но мне сказали, что
существует решение за O(n). Жду помощи! Если укажите направление движение, будет тоже
хорошо. Алгоритм должен быть реализован на С++ в виде ф-и.    

Ответы

Ответ 1

Более общая задача нахождения наибольшей общей подпоследовательности (для случая
двух последовательностей) решается динамическим программированием за O(N*M).
Родственная задача нахождения наибольшей общей подстроки в двух строках (алфавит
ограничен) решается суффиксными деревьями за O(N+M).
Думаю истина где-то рядом). По идее нужно использовать условие возрастания подпоследовательности.
Также стоит посмотреть на суффиксные деревья.


Ответ 2

Мне кажется, что где-то здесь вкралась ошибка или неточность формулировки. Даже задача
нахождения наибольшей возрастающей подпоследовательности одной данной последовательности
решается в общем случае за O(n log n), а тут требуется за O(n + m) найти наибольшую
общую такую подпоследовательность для 
пары последовательностей?
Может быть, имелись в виду всё-таки подстроки? Если исходные последовательности возрастают,
то решение уже было приведено. Если нет, то можно поделить их на возрастающие участки
(ответ не может пересекать границу таких участков) и попробовать достичь нужной асимптотики
(не знаю, получится ли). Также можно действительно применить суффиксные деревья, точнее,
этот алгоритм. Вроде бы, его несложно модифицировать для возрастающих подстрок, идя
только по возрастающим путям в дереве.


Ответ 3

У меня получилось решить только за O(n^2). Думаю, намного быстрее не получится.
вот код
int comlen( char *p, char *q) {
    int maxlen = 0;
    while ( (*p != '\0' || *q != '\0' ) && *p++ == *q++)
         ++maxlen;
    return maxlen;
}
int isInc( char *p, int len) {
    int i = 1;
    int k = 0;
    for (; *p != '\0' && i < len; ++i, ++k) {
         if (p[i] maxlen) {
                       maxlen = thislen; 
                       maxi = i;
                       maxj = j;
                   }
               }
         }
    }
    return maxlen;
}


Ответ 4

Есть алгоритм 0(n~m). Что-то между n и m.
Смысл такой:


есть глобальные итераторы (или указатели) на:
начало в первой последовательности, первоначально = 0
начало во второй последовательности, первоначально = 0
длина последовательности, первоначально = 0


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

длинна последовательности, первоначально = 0
есть какие-то текущие указатели и условие цикла


   for (iterator i1 = listN.begin(), iterator i2=listM.begin(); i1!=listN.end() &&
i2!=listM.end(); )
   {
       if (мы не в общей подпоследовательности)
       {
          if (*il=*i2)
          {
             то начинаем новую подпоседовательность, заодно длина текущей подпоследовательности ++;
             ++i1;
             ++i2;
          }
          else
          {
             сдвигаем тот итератор, значение по которому меньше;
          }
       }
       else if (мы в общей подпоследовательности)
       {
          if (*il=*i2)
          {
             длина текущей подпоследовательности ++;
             ++i1;
             ++i2;
          }
          else
          {
             общая подпоследовательность закончилась,
             сравниваем ее с найденной глобальной; 
             если текущая больше глобальной, приравниваем глобальную текущей;
             ставим текущие начала последовательности в NULL, 
             а текущую длину подпоследоваельности в 0;
             сдвигаем тот итератор, значение по которому меньше;
          }
       }
   }



После прохода цикла в глобальных переменных будет лежать результат: если подпоследовательность
была,
тут итерируется либо оба итератора, если значения по ним равны, либо 1 из них, по
которому значение больше, до тех пор пока, не достигнут конец одного из списков.


Ответ 5

Предлагаю отдать должное этой статье: Длиннейшая возрастающая подпоследовательность
за O (N log N)