Suffix Tree

Find All Occurrences Of pi

•Search suffix tree for pi.
•Suppose the search for pi is successful.
•When search terminates at an element node, pi appears exactly once in the source string S.
•When the search for pi terminates at a branch node, each element node in the subtree rooted at this branch node gives a different occurrence of pi.

Longest Repeating Substring

•Find longest substring of S that occurs more than m > 1 times in S.
•Label branch nodes with number of element nodes in subtree.
•Find branch node with label >= m and max char# field.

Longest Sequential Repeating Substring

we simply need to look at each repeated substring (i.e. each non-leaf node), but before comparing its size to make sure it is the longest, we must first ensure that the string is repeated sequentially. To do this, we need to see if the repeated string (from the root to the current node) is contained in the child branches beginning at and emanating from the current node.

Longest Common Substring or Subsequence(LCS)

Given two strings S and T. S = carport, T = airports

  • Longest common substring = rport
  • Longest common subsequence = arport


`longest common substring problem’ is different to the `longest common subsequence problem’ which is closely related to the `edit-distance problem’: An instance of a subsequence can have gaps where it appears in txt1 and in txt2, but an instance of a substring cannot have gaps.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License