Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# isaiah-perumalla/subpalindrome.py

Last active Dec 19, 2015
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, longest+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'
to join this conversation on GitHub. Already have an account? Sign in to comment