Как можно быстро найти все возможные совпадения в тексте. Попробовал написать алгоритм, но даже на небольших файлах (~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
Потом нужно оставить совпадения с максимальным значением - количество_совпадений * длина_совпадения. Может это как-то можно сразу сделать?
Как можно ускорить поиск? Какие существуют алгоритмы для этого?