import itertools

#dirty hack to make slices hashable
def slice(*args):
    if len(args) == 1:
        return (args[0], args[0]+1)
    else:
        return tuple(args)

def at(s, slice):
    i,j = slice
    return s[i:j]

def overlaps(a,b):
    #returns True if slices a and b overlap, False otherwise.

    def overlaps_scalar(slice, idx):
        #returns True if the scalar index value falls within the boundaries of the slice.
        return slice[0] <= idx < slice[1]

    return overlaps_scalar(a, b[0]) or overlaps_scalar(a, b[1]-1) or overlaps_scalar(b, a[0]) or overlaps_scalar(b, a[1]-1)

#locate the slices of all right-semi-palindromes in a string.
#a semi-palindrome is a non-empty string that is one character short of a palindrome. Examples include "ABCDCB", "ACECAR", "GHHGF" and "XY"
#a right-semi-palindrome is a semi-palindrome whose missing character is at the right end. Examples include "ABCDCB", "FGHHG", and "XY"
def iter_right_semi_palindrome_slices(s):
    for delta in (0,1): #need to iterate twice to catch strings of odd and even length
        for i in range(len(s)-delta):
            j = i+delta
            yield slice(i,j+1)
            while i > 0 and j < len(s)-1 and s[i] == s[j+1]:
                i -= 1
                j += 1
                yield slice(i, j+1)

def iter_left_semi_palindrome_slices(s):
    s = s[::-1]
    for i,j in iter_right_semi_palindrome_slices(s):
        yield slice(len(s) - j, len(s) - i)

def find_palindrome_slices(s):
    d = {}
    for idx, c in enumerate(s):
        d.setdefault(c, []).append(slice(idx))

    pairs = set()
    #base case 1: len(p) == 1 and q is a left-semi-palindrome.
    for q in iter_left_semi_palindrome_slices(s):
        char = s[q[1]-1]
        for p in d[char]:
            if not overlaps(q, p):
                pairs.add((p,q))

    #base case 2: len(q) == 1 and p is a right-semi-palindrome.
    for p in iter_right_semi_palindrome_slices(s):
        char = s[p[0]]
        for q in d[char]:
            if not overlaps(p,q):
                pairs.add((p,q))

    inductive_pairs = set()
    #inductive case. find p' and q', which are p and q but with one additional character on the left or right respectively.
    for p,q in pairs:
        while True:
            p = slice(p[0]-1, p[1])
            q = slice(q[0], q[1]+1)
            if p[0] < 0 or q[1] > len(s): break
            if overlaps(p,q): break
            if s[p[0]] != s[q[1]-1]: break
            inductive_pairs.add((p,q))

    return pairs | inductive_pairs

s = "ABBA"
for p,q in find_palindrome_slices(s):
    print("=======================")
    print(" " * p[0] + "v"*(p[1] - p[0]))
    print(s)
    print(" " * q[0] + "^"*(q[1] - q[0]))

    p = s[p[0]:p[1]]
    q = s[q[0]:q[1]]
    print(f"{p} + {q} == {p+q}")