花弁

Доброкодер 25 November 2012 (Sun) 17:10 No.27400

File: -.jpg
Jpg, 172.83 KB, 1440×900 - Click the image to expand

Пришло время помогать быдлостудентам с задачами, быдлостуденты сами ничего не сделают
Привет, анон, есть две задачи, никак не могу придумать эффективный алгоритм для их решения. Собственно, задачи:
1)Имеется заданная пара длинных строк S и T (> 50000 символов). Необходимо
   составить строку T из подстрок строки S так, чтобы количество использованных
   подстрок S было минимальным. Подстроки строки S могут быть использованы несколько
   раз и могут "перекрываться".
   Пример:
   S = "abadefghijk"
   T = "jkadbaefgab"

   => T = "jk" + "ad" + "ba" + "efg" + "ab"
2)В заданной последовательности элементов найти подпоследовательность максимальной
   длины, обладающую следующим свойством: она должна быть разложима на две
   непересекающиеся последовательности - неубывающую и невозрастающую.

   Пример:
   S = "11231933921" ^^^^ ^^^^^^    Подходящая подпоследовательность (элементы выделены символом ^):
   "1123933921" ~ "112 9 9 " - неубывающая " 3 33 21" - невозрастающая В принципе первую можно было бы решить и в лоб, последовательно деля строку T на подстроки и проверяя, являются ли они подстроками S. Но не зря же в условии задан такой большой размер строк. А вторую я вообще не представляю, как решать, даже неэффективно.
Код не нужен, мы все равно еще многое не прошли, и я могу ничего не понять (классы, например, еще даже не начали). Просто алгоритм, а я уж реализую. Заранее спасибо.

Доброкодер 26 November 2012 (Mon) 16:23 No.27462

>>27448
По-моему, можно и шустрее.
Первый проход по строке - выделить возрастающие, убывающие, неубывающие и невозрастающие последовательности, максимальные для элементов, с которых они начинаются.
Второй проход - смотреть суммы неубывающей и убывающей или невозрастающей и возрастающей, оканчивающейся/начинающейся на текущем/следующем символе; если получится больше максимальной суммы, найденной раньше - запоминаем. В конце выводим результат.
Алсо, второй проход, возможно, можно включить и в первый. Будет O(n).

Доброкодер 26 November 2012 (Mon) 20:39 No.27470

>>27400
Вариант решения первой (псевдокод):
Для каждого символа T находишь длину максимальной подстроки в S:

поиск_максимальных_длин_подстрок(T, S):
    // возвращает список максимальных длин подстрок
    L = новый_список()
    для i от 1 до длина(Т):
        P = список_позиций_символа_в_строке(Т[i], S)
        если P пуст:
            задача нерешаема!
        макс_длина = 0
        пока P не пуст:
            макс_длина += 1
            для каждой позиция в P:
                если S[позиция + макс_длина] не равно T[i + макс_длина]:
                    удалить_элемент_из_списка(позиция, P)   
        добавить_элемент_в_список(макс_длина, L)
    вернуть L

Для твоего примера получится

S = "abadefghijk"
T = "jkadbaefgab"
L =  21212132121

При условии, что "список позиций символа в строке" рассчитан заранее для каждого символа (сложность расчета M * K) сложность всей функции в худшем случае (две строки из одного символа):O(0.5 * N * M^2) Память:Θ(N) где N - длина T, M - длина S, K - число символов

Далее «задача о расписании»: ищешь максимальной длины подстроку, добавляешь ее в ответ:

______efg__
jk____efg__
jkad__efg__
jkadbaefg__
jkadbaefgab

Доброкодер 26 November 2012 (Mon) 21:07 No.27474

>>27462
Погоди, а с чего ты взял, что невозрастающая и неубывающая подпоследовательности, на которые должны делиться искомая подпоследовательность, начинаются/оканчиваются с соседних элементов? Даже в примере они на половину как бы "проникают" друг в друга. И они не могут начинаться одновременно с одного и того же элемента, так как они не должны пересекаться.

Доброкодер 27 November 2012 (Tue) 00:03 No.27482

>>27481
Вот, кстати, алгоритм который действительно выдает O(N*M^2)
Опишем структуру Node
`struct Node
{
   const List string; // иммутабельный список чтобы не засирать память
   const int len; //длина этого списка
}`
Расположим эти структуры в двух массивах MxM - текущем и предыдущем. Индексы будут означать последние элементы подпоследовательностей - достаточную инфрмацию для оапределения допустимости добавления в них нового элемента
   Операция итерации выглядит так
1) происходит свап массивов и очистка "следующего"
2) для каждого элемента предыдущего массива производится попытка создать
а) копию
б) массив, где зачитаный элемент войдет в возрастающую подпоследовательность
в) массив, где зачитаный элемент войдет в убывающую подпоследовательность.
При этом в заполняемой клетке нового массива проверяется наличие длины, и если она больше либо равна нашей расчетной попытка считается неудачной.

Сложность алгорита O(N*M^2), затраты памяти O(M^2)

Доброкодер 27 November 2012 (Tue) 01:07 No.27492

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

Поиск наибольшей неубывающей последовательности быстрее за O(N*log(N)) не сделать.

>>27491
То, что решение правильное нужно ещё доказать, но для тестовых последовательностей [0000000, 0000001 ... 4444444] работает.

Доброкодер 27 November 2012 (Tue) 05:56 No.27497

>>27474

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

Не невозрастающая и неубывающая, а:

> неубывающей и убывающей или невозрастающей и возрастающей

Притом порядок значения не имеет.
>>27492 >>27495
Ну я говорил о наибольших, начинающихся и оканчивающихся на определённом элементе. Делается при одном проходе, с использованием счётчиков и записью результатов в соседние массивы.
>>27491
Но наибольшая неубывающая может и не являться частью наибольшей, разложимой на неубывающую и невозрастающую. Пример: 12221254321.

Доброкодер 27 November 2012 (Tue) 06:09 No.27498

>>27497

> Но наибольшая неубывающая может и не являться частью наибольшей, разложимой на неубывающую и невозрастающую

Алсо, если подразумевалось взятие наибольшей неубывающей или невозрастающей, то вот ещё пример: 12345123543254321
12345 и 54321 - наибольшие неубывающая и невозрастающая, но получаем из них только 123451 и 254321 (по 6), в то время как 1235432 даёт 7. Не понимат, что там по индукции в уме доказывается.
Извиняюсь, если что-то напутал и пишу глупости в тред, лол.

Доброкодер 27 November 2012 (Tue) 14:13 No.27505

>>27481

> Давай ка не на глазок, а точную апроксимацию

поиск_максимальных_длин_подстрок(T, S):
    // возвращает список максимальных длин подстрок
    L = новый_список() // C
    для i от 1 до длина(Т): // N раз
        P = список_позиций_символа_в_строке(Т[i], S) // С
        если P пуст:                                 
            задача нерешаема! // C
        макс_длина = 0        // C
        пока P не пуст: // в худшем случае M раз
            макс_длина += 1  // C            
            для каждой позиция в P: // в худшем случае M, M - 1, ..., 3, 2, 1
                если S[позиция + макс_длина] не равно T[i + макс_длина]: 
                    удалить_элемент_из_списка(позиция, P) // C
        добавить_элемент_в_список(макс_длина, L) // C
    вернуть L

Итого O(0.5 * N * M * (M + 1))

Доброкодер 27 November 2012 (Tue) 17:04 No.27514

>>27506

> 54321 ++ 2222 же ответ, наибольшая неубывающая 54321

Ох щи, условие невнимательно прочёл. Подумал, что нужно выделить последовательность подряд идущих элементов, которую можно разложить на неубывающую и невозрастающую, элементы которых тоже идут подряд. Пример из задания не посмотрел даже сразу, фэйл.

Доброкодер 27 November 2012 (Tue) 20:54 No.27519

>>27497
Ну хорошо, а почему именно неубывающая и убывающая или невозрастающая и возрастающая? В том же примере последовательности неубывающая и невозрастающая. И, кроме того, не факт, что именно максимальные для данных элементов последовательности должны составить искомую подпоследовательность. Ведь максимальные могут пересечься во многих местах, а по условию пересекаться они не должны.

Доброкодер 06 December 2012 (Thu) 20:08 No.27803

>>27684
Любая наибольшая неубывающая последовательность? Тогда вот тебе такой пример:
7278578
первая попавшаяся наибольшая неубывающая последовательность:
7 78 8
Из оставшихся элементов можно составить невозрастающую последовательность длиной только в 1 элемент. Получится подпоследовательность в 5 элементов. В то время как из исходной последовательности можно составить, например, такую подпоследовательность:
7278 78
278 8
7 7
Просто проверять для каждой наибольшей неубывающей последовательности? Так еще нужно доказать, что решение составляется именно так. Я вот так и не додумался, как ты по индукции доказывал.
>>27712
1 курс, "Практикум на ЭВМ".