Имеется задача. Найти наибольшую общую возрастающую последовательность среди двух последовательностей длинной n и m. Я написал алгоритм за O(n^2), но мне сказали, что существует решение за O(n). Жду помощи! Если укажите направление движение, будет тоже хорошо. Алгоритм должен быть реализован на С++ в виде ф-и.
5 ответов
Более общая задача нахождения наибольшей общей подпоследовательности (для случая двух последовательностей) решается динамическим программированием за O(N*M).
Родственная задача нахождения наибольшей общей подстроки в двух строках (алфавит ограничен) решается суффиксными деревьями за O(N+M).
Думаю истина где-то рядом). По идее нужно использовать условие возрастания подпоследовательности.
Также стоит посмотреть на суффиксные деревья.
Мне кажется, что где-то здесь вкралась ошибка или неточность формулировки. Даже задача нахождения наибольшей возрастающей подпоследовательности одной данной последовательности решается в общем случае за O(n log n), а тут требуется за O(n + m) найти наибольшую общую такую подпоследовательность для пары последовательностей?
Может быть, имелись в виду всё-таки подстроки? Если исходные последовательности возрастают, то решение уже было приведено. Если нет, то можно поделить их на возрастающие участки (ответ не может пересекать границу таких участков) и попробовать достичь нужной асимптотики (не знаю, получится ли). Также можно действительно применить суффиксные деревья, точнее, этот алгоритм. Вроде бы, его несложно модифицировать для возрастающих подстрок, идя только по возрастающим путям в дереве.
-
Задача нахождения наибольшей возрастающей подпоследовательности одной данной последовательности решается за O(n). 6 янв 2011 в 21:20
-
Боюсь, мне такой алгоритм не известен, и я даже уверен, что для данной задачи лучшая оценка, которую я встречал, именно O(n log(n)). Не могли бы вы привести ссылку на решение за O(n)? 6 янв 2011 в 21:35
-
Ссылки у меня нет. Я ее когда-то решал. У меня есть решение. Если Вы зададите вопрос, на вроде - как решить задачу о нахождения наибольшей возрастающей подпоследовательности одной данной последовательности за O(n), я обязательно выложу код.Все таки, в данном вопросе обсуждается другая задача. 6 янв 2011 в 22:00
У меня получилось решить только за 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]<p[k])
return 0;
}
return 1;
}
int lcis(char * str1, char * str2, int len) {
int maxlen = -1;
int thislen = -1;
int maxi = 0, maxj = 0;
for (int i = 0; i < len; ++i){
for (int j = 0; j < len; ++j) {
thislen = comlen( &str1[i], &str2[j]);
if (isInc(&str1[i], thislen)){
if (thislen > maxlen) {
maxlen = thislen;
maxi = i;
maxj = j;
}
}
}
}
return maxlen;
}
-
2Быть может, всё-таки за O(n^3)? Два вложенных цикла + вызов comlen, который осуществляет линейный поиск. Пример: 2 строки из символов 'a' длины n. 6 янв 2011 в 21:27
-
Опечатка. Да в худшем случае время будет порядка O(n^3), а в среднем O(n^2). Можно добавить условие выхода из цикла, к примеру, когда обе строки одинаковые (сравнить текущею длину с длиной мин. строки). 6 янв 2011 в 22:08
Есть алгоритм 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 из них, по которому значение больше, до тех пор пока, не достигнут конец одного из списков.
-
1Во-первых, это похоже на алгоритм поиска общей возрастающей подстроки, а не подпоследовательности (в подпоследовательности не обязательно элементы были соседними в исходной последовательности). Во-вторых, он вроде бы не всегда находит наибольший ответ. Пример: [9, 1, 2, 3] и [1, 2, 3, 9], он найдёт [9]. Вроде бы, он работает в том случае, если данные последовательности возрастают. 6 янв 2011 в 20:56
-
Из кода очевидно, что работает только для возрастающих последовательностей. Можно попробовать переделать, выделяя из глобальных последовательностей возрастающие части, а потом прогоняя через это. Но быстрее, чем спросившим предложенное, точно не будет. Upd.: ofitserov уже писал почти то же самое) 19 янв 2011 в 19:52
Предлагаю отдать должное этой статье: Длиннейшая возрастающая подпоследовательность за O (N log N)