Optimal discovery of subword associations in strings

Given a textstring x of n symbols and an integer constant d, we consider the problem of finding, for any pair (y, z) of subwords of x the number of times that y and z occur in tandem (i.e., with no intermediate occurrence of either one of them) within a distance of d symbols of x. Although in principle there might be n(4) distinct subword pairs in x, we show that it suffices to consider a family of only n(2) such pairs, with the property that for any neglected pair (y', z'), there is a corresponding pair (y, z) contained in our family and such that: (i) y' is a prefix of y and z' is a prefix of z, and (ii) the tandem index of (y', z') equals that of (y, z). We show that an algorithm for the construction of the table of all such tandem indices can be built to run in optimal O(n(2)) time and space.