Source file: quest3.c Input file: quest3.in Output file: quest3.out
Let T and P be two sequences t1, t2,..., tn and p1, p2,..., pk of characters, such that k <= n.
P is a subsequence of T if there is a sequence of indices 1 <= i1 < i2 < ... < ik <= n such that for all j, 1 <= j <= k, we have t(ij) = p(j).
Assume that the ith character of T has a positive cost c(i) associated with it. Desing a O(n) algorithm to find the matching consecutive subsequence that maximises the sum of costs. That is, find the sequence of indices 1 <= i1 < i2 < ... < ik <= n such that for all j, 1 <= j <= k, we have t(ij) = p(j), [ c(i1) + c(i2) + ... + c(ik) ] is maximised and i(j+1) = i(j) + 1.
The input data for this program consists of several instances. The number "x" of instances comes in the first line of the input file. For each instance, there is first one line containing the sequence T. In the second line of an instance comes n integers representing the costs of the caracters in T. In the last line of each instance, there will be the sequence P.
For each instance to be investigated, your program should first print the number of the instance as in the sample output. then, you should print the message "no matching" if P is not a subsequence a T or the indices of the sequence T which maximise the cost separated by only one white space (see the sample outuput).
A blank line should separate each instance in the output file.
2 casacasa 7 2 3 4 5 8 10 15 casa naotem 1 2 3 4 5 6 tinha
Instance #1 5 6 7 8 Instance #2 no matching