8.1 Approximate Pattern Matching with Jokers

In this section, we assume that the string x and the text y can contain occurrences of the letter , called joker, special letter that does not belong to the alphabet A.Thejoker ^[1] matches with itself as well as with all the letters of the alphabet A.

More precisely, we define the notion of correspondence on A ? { } as follows. Two letters a and b of the alphabet A ? { } correspond, what we denote by

if they are equal or if at least one of them is the joker. We extend this notion of correspondence to strings: two strings u and ? on the alphabet A ? { } and of the same length m correspond, what we denote by

if, at each position, their respective letters correspond, that is to say if, for i = 0 , 1 , , m ? 1,

The search for all the occurrences of a string with jokers x of length m in atext y of length n consists in detecting all the positions j on y for which x ? y [ j .. j + m ? 1].