Substrings ---------- You work for a new group doing DNA analysis, and have been asked to write a program that will accept a DNA string D and a large number of queries of the form How many times does string S appear as a substring of D and what are the starting locations of these appearances? In the long run both D and the number of queries will be very large, but in the first version of your program D will not be excessively large. Input ----- For each of several test cases, first a line containing just the test case name, then a possibly very long line containing the string D, then many lines each containing a query, and then a line containing just `*'. Each query line contains just the string S as it is in the query above. D and S are strings of the letters A, C, G, and T. 1 <= length D <= 20,000 1 <= length S <= 20,000 1 <= sum of length S over all queries <= 200,000,000 The test case name line contains at most 80 columns. Other lines contain at most 20,000 columns. Input ends with an end of file. Output ------ For each test case, first an exact copy of the test case name input line, and then for each query one answer line of the form L M p1 p2 ... pM where L is the length of the query input string S, M is the number of occurrences of S in D, and p1, p2, ..., pM are the positions of the M occurrences. M may equal 0. The first letter in D has position 0, the last has position `length D - 1'. The positions in a query answer line may be in any order but must not contain duplicates. Sample Input ------ ----- -- SAMPLE 1 -- AAAAAAAACCCCAAAAA AAA AAAAA AACC AACCCAA AACCCCAA AACCCCCAA CAAAAA CAAAAAA * -- SAMPLE 2 -- ACGGCACGTCGTGTACGTC AC ACG ACGT CT GT * Sample Output ------ ------ -- SAMPLE 1 -- 3 9 14 13 12 0 1 2 3 4 5 5 5 12 0 1 2 3 4 1 6 7 0 8 1 6 9 0 6 1 11 7 0 -- SAMPLE 2 -- 2 3 0 14 5 3 3 0 14 5 4 2 14 5 2 0 2 4 12 16 7 10 File: substrings.txt Author: Bob Walton Date: Wed Oct 5 05:05:03 EDT 2016 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file.