Find longest palindrome substring in linear time.

longest_palindrome.py

# 1. palindrome window the size of string
# 2. split the window in half (omit central character is window size is odd)
# 3. compare substrings
# 4. if substings are equal - they are the longest palindrome
# 5. else slide the window to the right and repeat
# 6. if sliding the window right overflows the string, decrease the window and start again.

def find_longest_palindrome(input):
    window_size = len(input)

    while window_size > 2:
        offset = 0
        while offset + window_size <= len(input):
            window = input[offset:offset+window_size]
            left = window[:window_size/2]

            if window_size % 2:
                # odd
                right = window[window_size - window_size/2:]
            else:
                right = window[window_size/2:]
            if left[::-1] == right:
                return window

            offset += 1

        window_size -= 1

if __name__ == '__main__':
    print find_longest_palindrome("abaccddccgefe")
    print find_longest_palindrome('abccbag')
    print find_longest_palindrome('abccba')
    print find_longest_palindrome('abbacdefg')
    print find_longest_palindrome('cdefg')