subpalindrome.py

#! /usr/bin/env python
# --------------
# User Instructions
#
# Write a function, longest_subpalindrome_slice(text) that takes
# a string as input and returns the i and j indices that
# correspond to the beginning and end indices of the longest
# palindrome in the string.
#
# Grading Notes:
#
# You will only be marked correct if your function runs
# efficiently enough. We will be measuring efficency by counting
# the number of times you access each string. That count must be
# below a certain threshold to be marked correct.
#
# Please do not use regular expressions to solve this quiz!

# def longest_subpalindrome_slice(text):
#     "Return (i, j) such that text[i:j] is the longest palindrome in text."
#     # Your code here
#     l = len(text)
#     r_max = 0
#     (low,up)=(i,j)=(0,0)
#     r=0
#     for m in range(l):
#         for r in range(min(m,l-m-1)):
#             print "(m,r,r_range):",(m,r,min(m,l-m-1))
#             (low,up)=(m-r,m+r)
#             if text[low]!=text[up]:
#                 if r>r_max:
#                     r_max = r
#                     (i,j)=(low+1,up-1)
#                 break
#         if r>r_max:
#             r_max = r
#             (i,j)=(low+1,up-1)
#     print (i,j)
#     print r_max
#     return (i,j)
#
#
# assert L('racecar') == (0, 7)


def longest_subpalindrome_slice(text):
    "Return (i, j) such that text[i:j] is the longest palindrome in text."
    if text == '': return (0,0)
    text=text.lower()
    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)]
    # print candidates
    return max(candidates, key=length)

def grow(text, start, end):
    "Start with a 0- or 1- length palindrome; try to grow a bigger one."
    while (start>0 and end<len(text)
           and text[start-1]==text[end]):
        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'

if __name__ == '__main__':
    print test()