Как бы я решал это на первом курсе:
0. Пускай на входе строка и массив из слов
1. Объявим какой-нибудь массив, куда будем скидывать найденные слова в строке.
2. Отсортируем исходный массив слов по длине
Берем какую-то переменную-указатель на букву в строке, например j.
3. Ищем слово максимальной длины из вх. массива, которое входит в строку, начиная с позиции j.
3a. Если ничего не нашли и не дошли к концу строки, то j+=1
3b. Если ничего не нашли и дошли к концу строки, то закончить
3с. Если нашли, то передвинуть указатель на длину найденного слова, а найденное слово - в массив
>Рекурсивно
Уже не ДП.
Я быдло,и теорию динамического программирования прослушал, но как решать эту задачу на практике я тебе поясню.
Итак, первым деломимпортируешь любую библиотеку парсер-комбинаторов и задаешь свой словарь как грамматику в нотации Бекуса-Наура создаешь одномерный массив A из n+1 n-длинна строкилогических переменных. Нулевой элемент полагаешь истинным. Далее каждый i элемент массива полагаешь равным истине, если в словаре существует слово на которое заканчивается эта подстрока, и A[i - слово.длинна] == true. В противном случае A полагаешь равным false. В качестве ответа выводишь A[n]
> Ну я так и расписал в посте, просто кривожопо.
Получается, что для каждой буквы из исходной строки мы будем вызывать k раз поиск подстроки, который работает за O(n), получается общая сложность - O(n^2*k).
Ну эту можно на пальцах решить, а задачи о двумеррном динамическом программировании, вроде задач о стоке воды или поиска подпоследовательности вгоняют меня в уныние.
Надо написать конечный автомат. Ну или сортировку массива строк с бинарным поиском, для извращенцев. Ну или префиксный поиск какой-нибудь. И вообще, надо условие задачи читать внимательней.
Теперь я делаю руками вот так и говорю, что строка должна быть произвольной длины, а в качестве словаря ты должен использовать словарь Мюллера. Далее я вспоминаю, что мы принимаем сигнал от инопланетян, учащих язык, со скоростью 1 буква в сутки и нам жизненно необходимо успеть запалить ошибку как можно скорее, иначе нас всех пустят на опыты.
Через RegExp.
>Надо написать конечный автомат.
>импортируешь любую библиотеку парсер-комбинаторов и задаешь свой словарь как грамматику в нотации Бекуса-Наура
Вы не правы. Рантайм LL парсера или конечного автомата (что в принципе одно и то же) - полиномальнен от входной строки, но у нас же произвольное количество строк (словарь - входные данные), и мы должны этот парсер построить в рантайме. И там уже сложность, вангую, не полиномальная.
Для бинарного поиска O(n × lb (S) + n), где n - длина строки, S - размер словаря. Откуда у вас n^2 вылез?
Любая нерекурсивная реализация динамического алгоритма переделывается в рекурсивную с хранением решенных подзадач в хэштаблице. Дискасс
Вы что-то попутали, сударь. Любая рекурсивная функция переделывается в итеративную с хранением промежуточных результатов в стэке. Если не переделывается, значит она невычислима. Первый курс шараги.
Тем более что рекурсивным говнокодом можно и стек переполнить.
Говнокодом можно и самопальный стэк переполнить, память-то не резиновая. Тут вон люди строку бесконечной длины в массиве хранить собираются.
Из строки произвольной длинны можно добыть её длинну -_-. Если это не строка, а бесконечный поток символов -- используй стримы вместо массивов, или ArrayBuffer, что, пожалуй, предпочтительней.
Никаких ограничений связанных с размерами и видом словаря нету. Ну, кроме его конечности.
Конечный автомат не сработает из-за неодозначности интерпретации.
Например для строки
IWELL
И словоря состоящего из {I, we, well} после получения "I" ты найдешь слово "we" а затем не найдешь сопоставления для ll
O(n^2*log m), скорее, (m- количество слов в словаре)
>Вгоняют в уныние
Ничего не поделаешь, дрочи скилл. Всегда ищи подзадачу к которой можно свести задачу
Я про другое. Все реализации динамического алгоритмов отвергают использование рекурсии, т.к. на лицо будет множественный вызов решения одной и той же подзадачи с теми же самыми параметрами. Т.е., если развернуть рекурсию в цикл, то некоторое подмножество итераций оного будет решать одну и ту же задачу. Моя же идея - применять таки рекурсию если угодно - развернутую, не суть с кэшированием уже полученных результатов решения подзадач.
Мемоизация?
Это будет мемоизация, и этот подход дороже. В любом случа6е, это будет уже другой алгоритм
Есть, например, задачка пикрилейтед.
Я так понимаю, что надо проитерировать буквы во входной строке, затем свести задачу к тому, что чтобы посчитать Problem(n), надо убедиться что последние буквы совпадают с любым словарным словом (если нет - вернуть фолс) и решить подзадачу Problem (n - размер слова которое мы распознали, так?)
А потом создать массив solvedProblems = Problem (1....n), где вместо рекурсивного вызова Problem (i) мы обращаемся к массиву solvedProblem?
Если так, то почему у меня такие задачи вызывают нихуёвые сложности? Если не так, то как вообще решать?