Initialization phase
The cell is the smallest extensible component of a maximal pattern and the string can be viewed as a sequence of overlapping cells. If no don't care characters are allowed in the motifs then the cells are non-overlapping. The initialization phase has the following steps.
Step 1: Construct patterns that have exactly two solid characters in them and separated by no more than D spaces or "." characters. This is done by scanning the string s from left to right. Further, for each location we store start and end position of the pattern. For example, if s = abzdabyxd and K = 2, D = 2, then all the patterns generated at this step are: ab, a.z, a..d, bz, b.d, b..a, zd, z.a, z..b, da, d.b, d..y, a.y, a..x, by, b.x, b..d, yx, y.d, xd, each with its occurrence list. Thus ab = {(1, 2), (5, 6)}, a.z = {(1, 3)} and so on.
Step 2: The extensible cells are constructed by combining all the cells with at least one dot character and the same start and end solid characters. The location list is updated to reflect the start and end position of each occurrence. Continuing the previous example, b-d is generated at this step with b-d = {(2, 4), (6, 9)}. All cells m with |m| <K are discarded. In the example, the only surviving cells are ab, b-d with ab = {(1, 2), (5, 6)} and b-d = {(2, 4), (6, 9)}