CF86C Genetic engineering

"Multidimensional spaces are completely out of style these days, unlike genetics problems" — thought physicist Woll and changed his subject of study to bioinformatics. Analysing results of sequencing he faced the following problem concerning DNA sequences. We will further think of a DNA sequence as an arbitrary string of uppercase letters "A", "C", "G" and "T" (of course, this is a simplified interpretation). Let $ w $ be a long DNA sequence and $ s_{1},s_{2},...,s_{m} $ — collection of short DNA sequences. Let us say that the collection filters $ w $ iff $ w $ can be covered with the sequences from the collection. Certainly, substrings corresponding to the different positions of the string may intersect or even cover each other. More formally: denote by $ |w| $ the length of $ w $ , let symbols of $ w $ be numbered from $ 1 $ to $ |w| $ . Then for each position $ i $ in $ w $ there exist pair of indices $ l,r $ ( $ 1

N/A

N/A

In the first sample, a string has to be filtered by "A". Clearly, there is only one such string: "AA". In the second sample, there exist exactly two different strings satisfying the condition (see the pictures below).