Substring palindromes

substring_palindromes.py

#!/usr/bin/env python3

''' Substring palindromes

    Find the number of ways a string can be split in a non-overlapping way
    such that p+q is a palindrome string. Two pairs (p,q) and (p',q') are
    treated as different iff p is chosen from different position from p' or
    q is chosen from diff position of q' .

    For example, take the string abba. The possible substrings which are
    palindrome can be formed from the pairs (p,q) resp. : ("a", "a"), ("a",
    "ba"), ("a", "bba"), ("ab", "a"), ("ab", "ba"), ("abb", "a"), ("b", "b")
    and we get: aa, aba, abba, aba, abba, abba, bb resp.
    so the answer is 7 

    From https://chat.stackoverflow.com/transcript/6?m=45897848#45897848

    Basic brute-force algorithm :(

    Written by PM 2Ring 2019.04.11
'''

def substrings(s):
    ''' Generate all the substrings of `s` '''
    length = len(s)
    for i in range(length):
        for j in range(i + 1, length + 1):
            yield s[i:j]

def make_palindromes(input_string):
    results = set()
    for i in range(len(input_string)):
        head = input_string[i:]
        for j in range(len(head) - 1):
            p, tail = head[:j+1], head[j+1:]
            for q in substrings(tail):
                s = p + q
                if s == s[::-1]:
                    results.add((p, q))
    return results

src = 'abba'
results = make_palindromes(src)
print(results, len(results))