First speedy solution for The Longest Palindromic by lezeroq - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

First solution in Speedy category for The Longest Palindromic by lezeroq

def longest_palindromic(text):
    """
    Use Manacher's algorithm
    """
    data = "|%s|" % ("|".join(text))
    right, center = 0, 0
    m, n = 0, 0

    d_len = len(data)
    length = [0] * d_len

    for i in range(d_len):
        len_i = max(1, min(length[2 * center - i], right - i))

        while (
            len_i <= i and len_i < d_len - i
            and data[i - len_i] == data[i + len_i]
        ):
            len_i += 1

        if right < len_i + i:
            right = len_i + i
            center = i
            if right - center > n - m:
                m, n = center, right

        length[i] = len_i

    return "".join([x for i, x in enumerate(data[2 * m - n + 1:n]) if i % 2])

if __name__ == '__main__':
    assert longest_palindromic("artrartrt") == "rtrartr", "The Longest"
    assert longest_palindromic("abacada") == "aba", "The First"
    assert longest_palindromic("aaaa") == "aaaa", "The A"

March 2, 2016

Comments:

veky on March 3, 2016, 1:52 p.m.
Thanks. Now I don't have to explain my code as much. :-DD (Though my algo is a bit more complicated.) Few nitpicks: implementation note (line 3) is a comment, not a docstring. Comments are for people reading source, docstrings are for people using your function. Not the same. :-) And, line 29: <pre class='brush: python'>return data[2*m-n+1:n:2] </pre> ;-)

lezeroq on March 3, 2016, 9:19 p.m.
Thanks. That's why I like a code review, there is always someone who helps to make the code better. But it's always remained something to improve. E.g. line 16 <pre class='brush: python'>len_i <= i < d_len - len_i </pre>

veky on March 4, 2016, 5:52 a.m.
Of course, but I'm not happy with that either. Much better would be to use EAFP, but this is complicated by list being too helpful and treating negative indices as valid from the end. The real solution (though a bit too complicated) is probably to use a local function: <pre class='brush: python'>def data_at(i): if i in range(len(data)): return data[i] while data_at(i - len_i) == data_at(i + len_i) is not None: </pre>

My3bka on July 23, 2019, 8:52 a.m.
you dont need it (data = text): <pre class='brush: python'>data = "|%s|" % ("|".join(text)) </pre> and kill at the end: <pre class='brush: python'>if i % 2 </pre>

Strings Theory

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.