Соответствует самой длинной ведущей подстроке

Question

Я ищу, чтобы вернуть наилучшее соответствие списка против коллекции списков.

x соответствует списку в коллекции, если список в коллекции длины n соответствует первым n элементам x.

например. [1,2,3] матчи с [1,2], но [1,2] не соответствует [1,2,3].

Я хочу, чтобы функция возвращала «лучшее» соответствие, то есть совпадение, которое является самым длинным.

например.

bestMatch [1,2,3,3] [[1],[1,2,3],[1,2],[1,2,3,2],[1,2,3,4]] == Just [1,2,3] 

Очевидно, что список здесь не самая лучшая структура данных, и я предпочел бы использовать стандартную структуру и поиск, а не катить свои собственные, какие-либо идеи, что я должен использовать и каким образом?

Я не думаю, что таблицы хэша будут работать, потому что совпадения не точны. Затем я подумал о поиске по упорядоченному дереву, но проблема в том, что если я ищу [1,2,100], я получу [1,2,99], [1,2,98], ... и т.д., прежде чем получить правильный ответ [1,2]. Может использовать хэш хешей (и так далее по дереву), но это похоже на много накладных расходов.

(Реализация на основе списка линейного поиска here)

Answer 1

Trie будет хорошим решением. В вашем случае значения будут равны (), что означает, что данный узел соответствует концу списка. Затем, учитывая список, вы просто пройдете trie как можно дальше, и последнее встреченное значение будет отмечать самый длинный сопоставленный список.

ByteString основы Trie в Data.Trie предлагает match, который, как представляется, именно то, что вы ищете (если 8-байтовые си ключи будут достаточно для вас):

-- | Given a query, find the longest prefix with an associated value in 
-- the trie, returning that prefix, it's value, and the remaining string. 
match :: Trie a -> ByteString -> Maybe (ByteString, a, ByteString) 

Существуют также другой пакет list-tries, который имеет более общие ключи. Я не уверен, есть ли такая функция, как match выше, но определенно можно было бы ее реализовать.