Вот рабочее решение на Хаскеле. Я назвал уникальные подстроки символами , а ассоциацию одного вхождения подстрок размещения . Я также интерпретировал критерий 3 («Используйте как можно меньше различных подстрок») как «используйте как можно меньше символов», а не «используйте как можно меньше мест размещения».
Это динамическое программирование подход; фактическое сокращение происходит из-за памятки. Теоретически, умная реализация haskell может сделать это за вас (но есть другие способы , где вы заключаете makeFindBest), я бы предложил использовать битовое поле для представления используемых символов и просто целое число для представления оставшаяся строка. Оптимизация возможна из-за того, что: при заданных оптимальных решениях для строк S1 и S2, которые оба используют один и тот же набор символов, если S1 и S2 объединены, тогда два решения могут быть объединены аналогичным образом, и новое решение будет оптимальный. Следовательно, для каждого раздела входной строки makeFindBest нужно оценивать только один раз в постфиксе для каждого возможного набора символов, используемого в префиксе.
Я также интегрировал обрезку ветвей и границ , как предложено в ответе Даниэля; это использует функцию оценки, которая становится хуже, чем больше символов пропускается. Стоимость монотонна по количеству обработанных символов, поэтому, если мы нашли набор мест размещения, на которые было потрачено впустую только альфа символов, то мы никогда больше не будем пытаться пропустить более альфа символов .
Где n - длина строки, а m - количество символов, наихудший случай - O ( m ^ n ), а m - O (2 ^ * * п тысячу тридцать один ). Обратите внимание, что удаление ограничения 3 сделает вещи намного быстрее: для запоминания потребуется только параметризация оставшейся строкой, которая является кэшем O ( n ), а не O ( n ). * 2 ^ м )!
Используя алгоритм поиска / сопоставления строк , такой как Алгоритм сопоставления строк Ахо-Корасика , улучшает шаблон consume / drop 1, который я здесь использую, от экспоненциального до квадратичного. Однако это само по себе не исключает факторного роста в комбинациях совпадений, в котором динамическое программирование помогает.
Также обратите внимание, что ваш 4-й "и т. Д." Критерии могут сильно изменить проблему, если она ограничивает проблему таким образом, чтобы сделать возможным более агрессивное сокращение или требует возврата назад!
module Main where
import List
import Maybe
import System.Environment
type Symbol = String
type Placement = String
-- (remaining, placement or Nothing to skip one character)
type Move = (String, Maybe Placement)
-- (score, usedsymbols, placements)
type Solution = (Int, [Symbol], [Placement])
-- invoke like ./a.out STRING SPACE-SEPARATED-SYMBOLS ...
-- e.g. ./a.out "abcdeafghia" "a bc fg"
-- output is a list of placements
main = do
argv <- System.Environment.getArgs
let str = head argv
symbols = concat (map words (tail argv))
(putStr . show) $ findBest str symbols
putStr "\n"
getscore :: Solution -> Int
getscore (sc,_,_) = sc
-- | consume STR SYM consumes SYM from the start of STR. returns (s, SYM)
-- where s is the rest of STR, after the consumed occurrence, or Nothing if
-- SYM isnt a prefix of STR.
consume :: String -> Symbol -> Maybe Move
consume str sym = if sym `isPrefixOf` str
then (Just (drop (length sym) str, (Just sym)))
else Nothing
-- | addToSoln SYMBOLS P SOL incrementally updates SOL with the new SCORE and
-- placement P
addToSoln :: [Symbol] -> Maybe Placement -> Solution -> Solution
addToSoln symbols Nothing (sc, used, ps) = (sc - (length symbols) - 1, used, ps)
addToSoln symbols (Just p) (sc, used, ps) =
if p `elem` symbols
then (sc - 1, used `union` [p], p : ps)
else (sc, used, p : ps)
reduce :: [Symbol] -> Solution -> Solution -> [Move] -> Solution
reduce _ _ cutoff [] = cutoff
reduce symbols parent cutoff ((s,p):moves) =
let sol = makeFindBest symbols (addToSoln symbols p parent) cutoff s
best = if (getscore sol) > (getscore cutoff)
then sol
else cutoff
in reduce symbols parent best moves
-- | makeFindBest SYMBOLS PARENT CUTOFF STR searches for the best placements
-- that can be made on STR from SYMBOLS, that are strictly better than CUTOFF,
-- and prepends those placements to PARENTs third element.
makeFindBest :: [Symbol] -> Solution -> Solution -> String -> Solution
makeFindBest _ cutoff _ "" = cutoff
makeFindBest symbols parent cutoff str =
-- should be memoized by (snd parent) (i.e. the used symbols) and str
let moves = if (getscore parent) > (getscore cutoff)
then (mapMaybe (consume str) symbols) ++ [(drop 1 str, Nothing)]
else (mapMaybe (consume str) symbols)
in reduce symbols parent cutoff moves
-- a solution that makes no placements
worstScore str symbols = -(length str) * (1 + (length symbols))
findBest str symbols =
(\(_,_,ps) -> reverse ps)
(makeFindBest symbols (0, [], []) (worstScore str symbols, [], []) str)