• API
• FAQ
• Tools
• Archive
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.

Top