Back
Close
  • 56

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

 Goal

You must find a substring corresponding to a DNA sequence gene inside another DNA sequence chr.
Because every individual is different, the gene can have delta differences of swapped characters with the aligned chr.

If the last characters of genes are out of the bounds of chr (chr is too short), it counts as a delta corresponding to the missing characters. No other removal or insertion of characters is allowed.

For example if gene is AATTAATTAATT and you only have one chr which is GAATTAACCAATTGGGGGGGGGG and the authorized delta is 3 then the output should be :
0 1 2
- 0 because it is the first (and only) chr matching
- 1 because the gene starts at the 2nd character of the chr
- 2 because 2 errors (delta) exists in the match (CC instead of TT)
Input
Line 1: An integer delta for the maximum number of difference accepted with the reference
Line 2: A string gene corresponding to the gene to search
Line 3: An integer n for the number of chr
Next n lines: A string chr corresponding to the DNA in which to search it
Output
3 integers space separated :
- The index of the chr the gene was found in
- The start index of gene in the chr
- The number of difference with the gene

Or in case of no match: NONE
Constraints
0 <= delta <= 10
length(gene) == 42
1 <= n <= 20
length(chr) == 128
Example
Input
0
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACCTCGTGGAGGAGGGTGTCTCCTGCTTGCTGAACATGACTAAAGAATTATTAAATTTTACGTAGGAAATCTTATGTCATAGGGGTG
Output
0 0 0

A higher resolution is required to access the IDE