0

Как можно быстро найти все возможные совпадения в тексте. Попробовал написать алгоритм, но даже на небольших файлах (~1024 байта) время поиска слишком огромное.

Код:

        local dataI = assert(io.open(select(2, ...), "r"))
        local data, dataLen = dataI:read("a")
        dataLen = #data
        local dataLen2 = math.floor(dataLen / 2)
        print("Data size: " .. dataLen)
        local function findMatches(len)
                for a = 1, dataLen2 - len + 1 do
                        partA = data:sub(a, a + len - 1)
                        for b = a + len, dataLen - len + 1 do
                                partB = data:sub(b, b + len - 1)
                                if partA == partB then
                                        print("!", partB)
                                end
                        end
                end
        end
        local len = dataLen2
        repeat
                findMatches(len)
                len = len - 1
        until len <= 0

Потом нужно оставить совпадения с максимальным значением - количество_совпадений * длина_совпадения. Может это как-то можно сразу сделать?

Как можно ускорить поиск? Какие существуют алгоритмы для этого?

1
  • 1
    да их множество. вы точно задачу сформулируйте, что значит "все возможные совпадения"
    – pavel
    Commented 20 мая 2018 в 19:46

1 ответ 1

0

Судя по приведенному коду, подойдёт связка суффиксный массив + алгоритм Касаи

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.