Suffix Trees & Repeated Subsequences

• Easy: track internal nodes – longest substring is given by maximum length internal-node substring

• Other internal nodes give repeated substrings

ABCQRABCSABTU$

Possible Extensions
Common substrings of two strings
Non-overlapping repetitions – requires augmented tree

Previous slide

Next slide

Back to first slide

View graphic version