2019 ICPC NENA (Quebec) Regional Qualifier

Start

2019-10-26 13:00 UTC

2019 ICPC NENA (Quebec) Regional Qualifier

End

2019-10-26 19:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -159 days 20:30:21

Time elapsed

6:00:00

Time remaining

0:00:00

Problem G
Match-Finding in DNA Sequences

The bases that comprise a strand of deoxyribonucleic acid (DNA) are commonly represented by the symbols A, C, G and T, and the strand itself by a string like

TACTGATCACGTGATCGAG

A researcher from the startup GeniFreeze has hired you to write code that will solve a particular problem that the team believes may lead to a cure for hypothermia.

They will provide you with a strand (in the form of a sequence like that shown above) and a list of markers (each of which is a genetic subsequence). Your program should report if there are non-empty substrings between the markers (and maintaining the given order provided by the list) that are all equal.

For example, if they send the strand shown above, and the list of markers

AC ACG GA

then your program should report that yes, the strand contains those markers emboldened and separated by spaces here:

T AC TGATC ACG TGATC GA G

and the substrings between those emboldened markers all equal TGATC. A particular input may lead to multiple successful outputs, and each success should be reported.

Input

The first line gives the subsequences that act as markers. Every input file has at least three markers. The second line gives the strand, which will have length at least three.

Output

If the program fails to find equal substrings between the markers, then the program should print:

Failed to find equal substrings between the markers.

If the program successfully finds equal substrings between the markers, then, for each successful outcome, the program should print:

Equal substrings found: <substring>

Sample Input 1 Sample Output 1
AC ACG GA
TACTGATCACGTGATCGAG
Equal substrings found: TGATC
Sample Input 2 Sample Output 2
TTT AAA CCC G
ACGTACGTACGTACGTACGTACGT
Failed to find equal substrings between the markers.
Sample Input 3 Sample Output 3
AAG GGT TTG
TAAGAGGTATTGGTAGGTATTTTGC
Equal substrings found: A
Equal substrings found: AGGTATT