Hard Matching
Time limit30sMemory limit1536 MB
Given a text sequence and two number patterns, count positions where consecutive-sum grouping matches each pattern, then find the smallest glue value x maximizing matches of the concatenated pattern with x inserted between them and report that match count.
- Level
Hard9 of 10
- Topics
- String matching, Prefix sum, Number theory, Binary search
- Solved
- No attempts yet
Problem
There is a text sequence T = t1, t2, ..., tn and a pattern sequence P = p1, p2, ..., pm, all made of positive integers.
In ordinary matching, P matches T at position k if p1 = tk, p2 = t(k+1), ..., pm = t(k+m-1). Such matches can be found with the Knuth-Morris-Pratt algorithm.
Here we define a harder kind of matching. P matches T at position k if there are indices k = a0 < a1 < ... < am satisfying the following conditions.
- t(a0) + t(a0+1) + ... + t(a1-1) = p1
- t(a1) + t(a1+1) + ... + t(a2-1) = p2
- ...
- t(a(m-1)) + t(a(m-1)+1) + ... + t(am-1) = pm
In other words, starting at position k, split the text into consecutive nonempty groups. The group sums must equal the pattern elements in order.
The number of matches is the number of distinct starting positions k where P matches T.
Given a text T and two patterns P1 and P2, compute the following four values.
- The number of matches of P1 in T
- The number of matches of P2 in T
- The smallest positive integer x that maximizes the number of matches of P1 · x · P2 in T. Here x is treated as a length-1 sequence, and · means sequence concatenation.
- The number of matches of P1 · x · P2 when x is the value found in item 3
Input
The first line contains the number of test cases C. Test cases may be separated by blank lines.
Each test case consists of six lines.
The first line contains the text length N.
The second line contains the N elements of the text.
The third line contains the length M1 of the first pattern.
The fourth line contains the M1 elements of the first pattern.
The fifth line contains the length M2 of the second pattern.
The sixth line contains the M2 elements of the second pattern.
N <= 11 * 10^6 and M1, M2 <= 2 * 10^6. In each test case, the sum of all elements contained in T, P1, and P2 does not exceed 22 * 10^6.
Output
For each test case, print one line containing the four required values in order, separated by spaces.
Hint
In the visible test, the first pattern matches at text positions 1, 2, 7, 8, 9, and 10.
The second pattern matches at positions 1, 2, 3, 7, 8, 9, 10, and 11.
The sequence 1, 1, 2, 48, 1, 1, 1 matches at text positions 1 and 2.
For 1 <= x < 47, the sequence 1, 1, 2, x, 1, 1, 1 matches nowhere.
The sequence 1, 1, 2, 47, 1, 1, 1 matches only at text position 2.
For x > 48, no sequence 1, 1, 2, x, 1, 1, 1 matches in three places.