Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
simple linear time algorithm for finding longest palindome substring in a give string
def longest_subpalindrome_slice(s):
longest=(0,0)
start_idx=0 #index of palindrone ending at i
repeated = True
#loop invariant we know longest palindrome in s[0:i]
#and we know longest palidrom ending at i
for i in xrange(1,len(s)):
if(start_idx != 0 and s[start_idx-1] == s[i]) :
start_idx = start_idx-1
repeated = False
elif (not repeated or s[i] != s[i-1]):
start_idx = i
repeated = True
longest = max(longest, (start_idx,i),key=lambda(l,r): r-l)
return (longest[0], longest[1]+1)
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)
assert L('hannnnah') == (0, 8)
assert L('abcerehannnnah') == (6, 14)
return 'tests pass'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment