Problem B

Either you are paranoid, or the CIA is sending you hidden messages in the newspaper. Every day you find an article that has a message hidden by separating its characters with other letters. You go through the article, circling every few characters, until the message is revealed. However, this is a tedious process, so you would love to write a program to ease the burden.

You are given a text and a target string (the hidden message). You must write a program that finds the shortest substring of characters in the text that contains the target string as a (not necessarily contiguous) subsequence.


The input consists of some number of pairs of texts and targets, each on their own line. The end of the file indicates the end of the input. The text and target are separated by an equals sign ($=$). The target will always appear in the text. The text will contain at most $10\, 000$ characters.


For each text/target pair, you should output the start and end indices, separated by a space, of the shortest substring of the text that contains the target as a (not necessarily contiguous) subsequence. Indices into the text start at $0$. If the target appears more than once with the same length subsequence, you should output the indices of the first appearance.

Sample Input 1 Sample Output 1
don't forget dozens of hotdogs=food
this is not a conspiracy theory "at the moment".=tin hat
3 5
3 7
6 26
12 15
0 34
CPU Time limit 9 seconds
Memory limit 1024 MB
Tom Helmuth
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in