SHARE
TWEET

Untitled

a guest Jun 27th, 2017 95 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. """
  2. ======================================
  3. (C) abs|Zer0| Nov 2010
  4. ======================================
  5. Practice Dynamic Programming
  6. Longest palindromic subsequence
  7.  
  8. +Given string: x1,x2,....,xn
  9.  
  10. + denotes m[i][j] : length of the longest palindromic subsequence
  11. + s: matrix for tracing the sequence
  12.  
  13. Recurrence Relation:
  14. m[i][j]  = 1 if i = j (a character itself is a palindromic subsequence with length 1)
  15. m[i][j]  = { * m[i+1][j-1] + 2 if xi = xj
  16.             * max( m[i+1][j], m[i][j-1]) if xi <> xj
  17.          
  18. """
  19. import sys
  20. st = "ILLINOISURBANACHAMPAIGN"
  21. n = len(st)
  22. m = [[0] * n for i in range(n)]  #define a matrix n*n with all set to 0
  23. s = [["."] * n for i in range(n)]
  24.  
  25. #(a character itself is a palindromic subsequence with length 1)
  26. for i in range(0, n):
  27.     m[i][i] = 1
  28.     s[i][i] = "/"
  29.    
  30. for x in range(1, n):
  31.     for i in range(0, n):
  32.     j = i + x
  33.     if j < n:
  34.        
  35.         if st[i] == st[j]: # xi == xj here
  36.         m[i][j] = m[i+1][j-1] + 2 # increase longest palindromic subsequence length by 2
  37.         s[i][j] = "/" #trace path
  38.         else:
  39.         if m[i+1][j] >= m[i][j-1]:
  40.             m[i][j] = m[i+1][j]
  41.             s[i][j] = "^"
  42.         else:
  43.             m[i][j] = m[i][j-1]
  44.             s[i][j] = ">"
  45.  
  46. #print out the longest palindromic subsequence string
  47. def print_path(st, m, s, i, j):
  48.     ret = [""] * m[i][j] #a return string is length of m[0][n]
  49.    
  50.     # 2 string pointers point to begin and end of the return string    
  51.     idx = 0
  52.     idx2 = len(ret) - 1
  53.  
  54.     while True:
  55.     if i > j:
  56.         break
  57.     if s[i][j] == '/': #if found 2 same chars
  58.         ret[idx] = st[i] #append to the beginning and the end of the return string
  59.         ret[idx2] = st[j]
  60.         idx += 1  #move the pointer of return string
  61.         idx2 -= 1
  62.        
  63.         i = i + 1 #move the pointer of the s matrix
  64.         j = j - 1
  65.     elif s[i][j] == '>':
  66.         i = i
  67.         j = j - 1
  68.     else:
  69.         i = i + 1
  70.         j = j
  71.        
  72.     print ret #print out result
  73.  
  74. print_path(st, m, s, 0, n-1)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top