Fig. 2

Search scheme by Kucherov et al. that allows up to 2 errors. The search scheme consists of three searches: \({\mathcal {S}}_0 = (012, 012, 022)\), \({\mathcal {S}}_1 = (210, 000, 012)\) and \({\mathcal {S}}_2 = (102, 001, 012)\). For each search, the processing order (from dark to light) and the lower and upper bounds for the cumulative number of errors after processing each part are indicated in the cells representing the parts. The arrows indicate the search direction (left-to-right or right-to-left). Search \({\mathcal {S}}_2\) for example, starts with the exact matching of the middle piece \(P_{\pi [0]} = P_1\). Second, the match is extended to the left (\(P_{\pi [1]} = P_0\)), and third, to the right (\(P_{\pi [2]} = P_2\)). After processing part \(P_0\) (and \(P_1\)), 0 or 1 errors should have been encountered. Similarly, after processing part \(P_2\) and \(P_0\) (and \(P_1\)), 1 or 2 errors should have been encountered. In summary, search \({\mathcal {S}}_2\) covers the following error distributions: [0, 0, 1], [0, 0, 2], [1, 0, 0] and [1, 0, 1]. It can be verified that every possible distribution of 2 errors among the three parts is covered by at least one of the three searches