Finding the longest subpalindrome in a piece of text

pals.py

# Finding the start and finish indexes of the
# longest subpalindrome of a given string.



# My solution - does war & peace in approx 3.2 sec on my 2.4GHz macbook
def longest_subpalindrome_slice(text):

    text = text.lower()
    textlen = len(text)
    textlen1  = textlen - 1
    textrange = xrange(textlen)

    def indlen(t):
        return t[1] - t[0]

    def expand(pals):
        expanded = [(s - 1, f + 1) for (s, f) in pals
                    if s > 0 and f < textlen and text[s - 1] is text[f]]
        return max(pals, key = indlen) if expanded == [] else expand(expanded)

    def seed():
        for i in textrange:
            yield (i, i + 1)
            if i < textlen1 and text[i] is text[i + 1]:
                yield (i, i + 2)

    return (0, 0) if textlen is 0 else expand([p for p in seed()])



# Peter's solution - does war & peace in approx 10.5 sec on my 2.4GHz macbook
def longest_subpalindrome_slice2(text):

    if text == '': return (0,0)
    def length(slice): a,b = slice; return b-a
    candidates = [grow(text, start, end)
                  for start in range(len(text))
                  for end in (start, start+1)]
    return max(candidates, key = length)

def grow(text, start, end):
    
    while (start > 0 and end < len(text)
           and text[start-1].upper() == text[end].upper()):
        start -= 1; end += 1
    return (start, end)



def test():
    L = longest_subpalindrome_slice
    
    assert L('racecar') == (0, 7)
    assert L('Racecar') == (0, 7)
    assert L('RacecarX') == (0, 7)
    assert L('Race carr') == (7, 9)
    assert L('') == (0, 0)
    assert L('something rac e car going') == (8,21)
    assert L('xxxxx') == (0, 5)
    assert L('Mad am I ma dam.') == (0, 15)
    return 'tests pass'



def preprocess_file(filename):
    f = open(filename, 'r+')
    text = f.read()
    return ' '.join(text.split()) # remove multiple spaces



text = preprocess_file('war_and_peace.txt')

test()

print longest_subpalindrome_slice(text)