Самая длинная распространенная ошибка подстроки

Я сделал это до сих пор

function lcs(xstr, ystr)
        if xstr:len() == 0 or ystr:len() == 0 then
                return ""
        end
        x = xstr:sub(1,1)
        y = ystr:sub(1,1)
        xs = xstr:sub(2)
        ys = ystr:sub(2)
        if x == y then
                return x .. lcs(xs, ys)
        else
                l1 = lcs(xstr, ys)
                l2 = lcs(xs, ystr)
                if l1:len() > l2:len() then
                        return l1
                else
                        return l2
                end
        end
end

print(lcs("abcd", "bcd"))

к сожалению, он печатает только «d», а не «bcd», как ожидалось. Для меня это выглядит так, как будто строка «l2 = lcs(xs, ystr)» не была выполнена, потому что, если я добавлю отладочную печать в начале, она напечатает, что функция не вызывалась с аргументами «bcd» и «bcd», но я уверен, что значения в порядке после начала оператора else. Буду признателен за любую помощь.


algorithm lua longest-substring
person Jakub Tětek    schedule 27.02.2014    source источник
comment
Знаете ли вы, что ваша функция имеет экспоненциальную временную сложность?   -  person pkacprzak    schedule 27.02.2014
comment
Да. В любом случае, спасибо, что рассказали мне.   -  person Jakub Tětek    schedule 27.02.2014
comment
Вы знаете, как это исправить?   -  person pkacprzak    schedule 27.02.2014
comment
Да. Я знаю алгоритм со временем работы O(mn)   -  person Jakub Tětek    schedule 27.02.2014

Ответы (1)


arrow_upward
3
arrow_downward

Ваша переменная xs является глобальной

l1 = lcs(xstr, ys)
l2 = lcs(xs, ystr)

Первая строка искажает значение xs, используемое второй строкой.
Сделайте все ваши временные переменные (x, y, xs, ys, l1, l2) локальными.

person Egor Skriptunoff    schedule 27.02.2014