API tools faq
paste
Guest User

suffix_tree_dump

a guest
Dec 5th, 2012
285
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.59 KB | None | 0 0
raw download clone embed print report
  1. Building a suffix tree for string "aabaaabb"
  2. The problem: during step 6, only 1 split node (Node 6) was created, i.e. it's suffix link will be null.
  3. But in a correct suffix tree, the link for (Node 6) must be (Node 3). Because of that, the resulting tree looks like this:
  4.  
  5. ROOT. children: (3 (a), 10 (b))
  6. 3 (a) children: (6 (a), 4 (baaabb))
  7. 6 (a) children: (7 (abb), 8 (b))
  8. 7 (abb) children: ()
  9. 8 (b) children: (2 (aaabb), 9 (b)) link: 10(b)
  10. 2 (aaabb) children: ()
  11. 9 (b) children: ()
  12. 4 (baaabb) children: ()
  13. 10 (b) children: (5 (aaabb), 11 (b))
  14. 5 (aaabb) children: ()
  15. 11 (b) children: ()
  16.  
  17.  
  18. While CORRECT Suffix Tree must look like this:
  19. ROOT (); children: (Node 3 (a), Node 12 (b)); link: -1
  20. Node 3 (a); children: (Node 6 (a), Node 10 (b)); link: ROOT
  21. Node 6 (a); children: (Node 7 (abb), Node 8 (b)); link: Node 3 (a)
  22. Node 7 (abb); children: (); link: -1
  23. Node 8 (b); children: (Node 2 (aaabb), Node 9 (b)); link: Node 10 (b)
  24. Node 2 (aaabb); children: (); link: -1
  25. Node 9 (b); children: (); link: -1
  26. Node 10 (b); children: (Node 4 (aaabb), Node 11 (b)); link: Node 12 (b)
  27. Node 4 (aaabb); children: (); link: -1
  28. Node 11 (b); children: (); link: -1
  29. Node 12 (b); children: (Node 5 (aaabb), Node 13 (b)); link: ROOT ()
  30. Node 5 (aaabb); children: (); link: -1
  31. Node 13 (b); children: (); link: -1
  32.  
  33. The steps of your approach are:
  34.  
  35. Step 1. BEFORE adding 'a'---------------------------------------------
  36. active_point: (1, 'a', 0), remainder: 1
  37.  
  38. AFTER adding 'a'
  39. active_point: (1, 'a', 0), remainder: 0
  40.  
  41. -------TREE IS:-------
  42. ROOT. children: (2 (a))
  43. 2 (a) children: ()
  44. --------------------------------------------------------------
  45.  
  46. Step 2. BEFORE adding 'a'---------------------------------------------
  47. active_point: (1, 'a', 0), remainder: 1
  48.  
  49. AFTER adding 'a'
  50. active_point: (1, 'a', 1), remainder: 1
  51.  
  52. -------TREE IS:-------
  53. ROOT. children: (2 (aa))
  54. 2 (aa) children: ()
  55. --------------------------------------------------------------
  56.  
  57. Step 3. BEFORE adding 'b'---------------------------------------------
  58. active_point: (1, 'a', 1), remainder: 2
  59.  
  60. AFTER adding 'b'
  61. active_point: (1, 'b', 0), remainder: 0
  62.  
  63. -------TREE IS:-------
  64. ROOT. children: (3 (a), 5 (b))
  65. 3 (a) children: (2 (ab), 4 (b))
  66. 2 (ab) children: ()
  67. 4 (b) children: ()
  68. 5 (b) children: ()
  69. --------------------------------------------------------------
  70.  
  71. Step 4. BEFORE adding 'a'---------------------------------------------
  72. active_point: (1, 'b', 0), remainder: 1
  73.  
  74. AFTER adding 'a'
  75. active_point: (3, '', 0), remainder: 1
  76.  
  77. -------TREE IS:-------
  78. ROOT. children: (3 (a), 5 (ba))
  79. 3 (a) children: (2 (aba), 4 (ba))
  80. 2 (aba) children: ()
  81. 4 (ba) children: ()
  82. 5 (ba) children: ()
  83. --------------------------------------------------------------
  84.  
  85. Step 5. BEFORE adding 'a'---------------------------------------------
  86. active_point: (3, '', 0), remainder: 2
  87.  
  88. AFTER adding 'a'
  89. active_point: (3, 'a', 1), remainder: 2
  90.  
  91. -------TREE IS:-------
  92. ROOT. children: (3 (a), 5 (baa))
  93. 3 (a) children: (2 (abaa), 4 (baa))
  94. 2 (abaa) children: ()
  95. 4 (baa) children: ()
  96. 5 (baa) children: ()
  97. --------------------------------------------------------------
  98.  
  99. Step 6. BEFORE adding 'a'---------------------------------------------
  100. active_point: (3, 'a', 1), remainder: 3
  101.  
  102. AFTER adding 'a'
  103. active_point: (6, '', 0), remainder: 2
  104.  
  105. -------TREE IS:-------
  106. ROOT. children: (3 (a), 5 (baaa))
  107. 3 (a) children: (6 (a), 4 (baaa))
  108. 6 (a) children: (7 (a), 2 (baaa))
  109. 7 (a) children: ()
  110. 2 (baaa) children: ()
  111. 4 (baaa) children: ()
  112. 5 (baaa) children: ()
  113. --------------------------------------------------------------
  114.  
  115. Step 7. BEFORE adding 'b'---------------------------------------------
  116. active_point: (6, '', 0), remainder: 3
  117.  
  118. AFTER adding 'b'
  119. active_point: (6, 'b', 1), remainder: 3
  120.  
  121. -------TREE IS:-------
  122. ROOT. children: (3 (a), 5 (baaab))
  123. 3 (a) children: (6 (a), 4 (baaab))
  124. 6 (a) children: (7 (ab), 2 (baaab))
  125. 7 (ab) children: ()
  126. 2 (baaab) children: ()
  127. 4 (baaab) children: ()
  128. 5 (baaab) children: ()
  129. --------------------------------------------------------------
  130.  
  131. Step 8. BEFORE adding 'b'---------------------------------------------
  132. active_point: (6, 'b', 1), remainder: 4
  133.  
  134. AFTER adding 'b'
  135. active_point: (10, '', 0), remainder: 2
  136.  
  137. -------TREE IS:-------
  138. ROOT. children: (3 (a), 10 (b))
  139. 3 (a) children: (6 (a), 4 (baaabb))
  140. 6 (a) children: (7 (abb), 8 (b))
  141. 7 (abb) children: ()
  142. 8 (b) children: (2 (aaabb), 9 (b)) link: 10(b)
  143. 2 (aaabb) children: ()
  144. 9 (b) children: ()
  145. 4 (baaabb) children: ()
  146. 10 (b) children: (5 (aaabb), 11 (b))
  147. 5 (aaabb) children: ()
  148. 11 (b) children: ()
  149. --------------------------------------------------------------
Add Comment
Please, Sign In to add comment
Public Pastes
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!