Longest Common Subsequence and Palindromes
A solution for finding Palindromes is using the Longest Common Subsequence(LCS) algorithm on the string and its reversed version. In this example I implement the LCS algorithm with dynamic programming and return all the longest common subsequences Here is an Dynamic Programming implementation of the Longest Common Subsequence algorithm.
def findAllLCS(s1,s2): n = len(s1) m = len(s2) #For the length of longsest common substring c = [[0 for _ in range(m+1)] for _ in range(n+1)] #Path leading the longest length p = [[0 for _ in range(m)] for _ in range(n)] for i in range(n): for j in range(m): if s1[i] == s2[j]: c[i+1][j+1] = c[i][j]+1 elif c[i][j+1] > c[i+1][j]: c[i+1][j+1] = c[i][j+1] p[i][j] = 1 elif c[i][j+1] < c[i+1][j]: c[i+1][j+1] = c[i+1][j] p[i][j] = -1 else: c[i+1][j+1] = c[i+1][j] p[i][j] = 2 allstrs=set() getLCS(s1,p,allstrs,n-1,m-1,'') return list(allstrs)
def getLCS(s1,p,allstrs,n,m,cur_s): while n>=0 and m>=0: if p[n][m] == 0: cur_s=s1[n]+cur_s n -= 1 m -= 1 elif p[n][m] == 2: getLCS(s1,p,allstrs,n-1,m,cur_s) m -= 1 elif p[n][m] == 1: n-=1 else: #p[n][m] == -1 m-=1 allstrs.add(cur_s)
An important note is, not all longest LCS’s are palidrome. But there is at least one in the set of longest subsequences.
strs=['NYYNYNY','HEYHOE','NURSESRUN','XSSASDEQSASADASD'] for s in strs: print findAllLCS(s,s[::-1])
['NYYYN', 'NYNYY', 'YYNYY', 'YNYNY', 'YYNYN', 'NYNYN'] ['EYE', 'HYE', 'EOE', 'HYH', 'EYH', 'EHE', 'HEH'] ['NURSESRUN'] ['SSASQSASS', 'SADSASDAS', 'SADASADAS', 'SSASESASS', 'SSASDSASS']