Database Reference
In-Depth Information
q
= 6
:
There are no possible values of
j
, since 7/(9 +
j
) > 0
.
8 for every positive in-
teger
j
. The same holds for every smaller value of
q
.
i
= 2
:
Here,
p
= 8, so we require
q
≤ 8. Since the constraint (
q
+1)/(9+
j
) ≥ 0
.
8 does not
9. Thus, the only possible values of
j
and
q
when
i
= 2 are
(1)
q
= 8;
j
= 1.
(2)
q
= 8;
j
= 2.
(3)
q
= 7;
j
= 1.
i
= 3
:
Now,
p
= 7 and the constraints are
q
≤ 7 and (
q
+ 1)/(9 +
j
) ≥ 0
.
8. The only option
is
q
= 7 and
j
= 1.
Next, we must consider the case
p
<
q
. The additional constraint is
Again, consider each possible value of
i
.
i
= 1
:
Then
p
= 9, so we require
q
≥ 10 and 10/(
q
+
j
) ≥ 0
.
8. The possible values of
q
and
j
are
(1)
q
= 10;
j
= 1.
(2)
q
= 10;
j
= 2.
(3)
q
= 11;
j
= 1.
i
= 2
:
Now,
p
= 10, so we require
q
≥ 11 and 9/(
q
+
j
+ 1) ≥ 0
.
8. there are no solutions,
since
j
must be a positive integer.
i
= 3
:
As for
i
= 2, there are no solutions.
When we accumulate the possible combinations of
i
,
j
, and
q
, we see that the set of index
buckets in which we must look forms a pyramid.
Figure 3.15
shows the buckets in which
we must search. That is, we must look in those buckets (
x, j, q
) such that the
i
th symbol of
the string
s
is
x
,
j
is the position associated with the bucket and
q
the suffix length.
□
Figure 3.15
The buckets that must be examined to find possible matches for the string
s
=
acdefghijk
with
J
= 0.8
are marked with an x
