Finding Maximal Pairs with Bounded Gap
Gerth Stølting Brodal
April 1999 |
Abstract:
A pair in a string is the occurrence of the same substring
twice. A pair is maximal if the two occurrences of the substring cannot be
extended to the left and right without making them different. The gap of a
pair is the number of characters between the two occurrences of the
substring. In this paper we present methods for finding all maximal pairs
under various constraints on the gap. In a string of length
![]() ![]() ![]() ![]() Available as PostScript, PDF. |