Mirrored avenue

Half an avenue is already in the ground and the gate end cannot move. Every new sapling goes at the open end, so the question is how few will do.

The problem

A park's avenue runs from the lake to the gate. The trees already planted are recorded one letter each, read from the lake end towards the gate: b birch, l lime, o oak, r rowan. The gate end abuts the road and is finished — no tree goes past it, and no planted tree moves.

The finished avenue must read the same walking either way. The only freedom left is the lake end: saplings may be planted in front of the existing row, any number, any species. Plant as few as possible and report the finished avenue, again from the lake end. Put another way: return the shortest palindrome ending with row.

Input. row — species letters, the avenue as planted.

Output. The shortest palindrome having row as its suffix.

Example.

row = 'olobr'   ->  'rbolobr'

Only two saplings, r and b, though the row is five trees long: olo at the lake end is already symmetric, so it sits in the middle of the finished avenue and is not mirrored.

A second example, where nothing can be reused:

row = 'blrb'   ->  'brlblrb'

Only the single b at the lake end is symmetric, so three saplings are needed. The answer is not blrb prefixed by its whole reverse — that is eight trees.

Constraints.

• 0 <= len(row) <= 10^5
• row contains only the letters b, l, o, r
• an empty row is already finished

Hints

Approach

Brute force

Test the prefixes from longest to shortest against their own reverses and stop at the first palindrome. Each test costs up to n comparisons and there are n of them: about 5 × 10⁹ comparisons at n = 10⁵, half a minute for one avenue.

The insight

The saplings to plant are exactly the reverse of everything after the longest palindromic prefix, and that prefix is the longest border of the row joined to its own reverse.

A border is both a prefix and a suffix. A suffix of reverse(row) of length L is the reverse of the prefix of row of length L, so a border of length L means that prefix equals its own reverse — a palindrome. The precondition: no border may run across the seam and claim more than the whole row, which a separator outside the species alphabet prevents.

Algorithm

1. Return the empty string for an empty row.
2. Build mirrored, the row reversed.
3. Form probe = row + '#' + mirrored, with # never a species letter.
4. Build the prefix-function table over probe: table[i] is the longest proper prefix of probe[:i+1] that is also its suffix.
5. Read keep = table[-1], the longest palindromic prefix of row.
6. Return mirrored[:len(row) - keep] + row — the reverse of the tail row[keep:] planted in front.

Complexity

Time O(n): one pass to reverse and one to build the table over a string of length 2n + 1, linear by the amortised argument on the fallback counter. Space O(n) for the probe and its table.

Solution

"""Mirrored avenue — shortest palindrome ending with the row, via the prefix function."""


def prefix_table(text):
    """table[i] = length of the longest proper prefix of text[:i+1] that is also
    a suffix of it."""
    table = [0] * len(text)
    span = 0
    for i in range(1, len(text)):
        # invariant: span is the length of the best border of text[:i]
        while span and text[i] != text[span]:
            span = table[span - 1]
        if text[i] == text[span]:
            span += 1
        table[i] = span
    return table


def solve(row):
    if not row:
        return ""
    mirrored = row[::-1]
    # '#' is outside the species alphabet, so no border can cross the seam and
    # claim more than the whole row.
    probe = row + "#" + mirrored
    keep = prefix_table(probe)[-1]      # longest prefix of row that is a palindrome
    return mirrored[:len(row) - keep] + row

TESTS = [
    (("olobr",), "rbolobr"),
    (("blrb",), "brlblrb"),
    (("lool",), "lool"),
    (("oooo",), "oooo"),
    (("",), ""),
    (("b",), "b"),
    (("br",), "rbr"),
    (("blr",), "rlblr"),
    (("bloolb",), "bloolb"),
    (("rblool",), "loolbrblool"),
]

Pitfalls

• Taking the longest palindromic suffix. The saplings go at the lake end, so the reusable symmetry has to sit at that end too. On olobr the longest palindromic suffix is r, which suggests planting four trees and gives a nine-tree avenue instead of seven.
• Joining without the separator. On oooo the table over oooooooo reports a border of 7, so keep exceeds the row length and mirrored[:4 - 7] silently drops trees. With the # the border is 4 and nothing is planted.
• Assuming the reusable part has a fixed parity. The longest palindromic prefix of blrb has length 1 and that of lool has length 4; rounding a midpoint instead of reading the table gets one of the two wrong.

Variants

• Tremor signature — the same table, used to resume a search instead of to measure self-overlap.
• Palindromes — the centre-expansion toolkit, and when the O(n²) version is the right trade.