Abstract

Information retrieval and data compression are the two main application areas where the rich theory of string algorithmics plays a fundamental role􏰂 In this pap er􏰁 we consider one algorithmic problem from each of these areas and present highly e􏰀cient 􏰄linear or near linear time􏰅 algorithms for b oth problems􏰂 Our algorithms rely on augmenting the su􏰀x tree􏰁 a fundamental data structure in string algorithmics􏰂 The augmentations are nontrivial and they form the technical crux of this they consist of adding extra edges to su􏰀x trees􏰁 Acyclic Graphs 􏰄DAGs􏰅􏰂 Our algorithms construct these 􏰓su􏰀x DAGs􏰔 and manipulate them to solve the two problems e􏰀ciently􏰂.