어려운 매칭
시간 제한30초메모리 제한1536 MB
정수 수열로 이루어진 텍스트와 두 패턴이 주어질 때 연속 구간 합으로 패턴이 일치하는 시작 위치 수를 구하고, 두 패턴 사이에 넣을 값 x 중 일치 횟수를 최대화하는 가장 작은 x와 그때의 일치 횟수를 구합니다.
문제
양의 정수로 이루어진 텍스트 수열 T = t1, t2, ..., tn 과 패턴 수열 P = p1, p2, ..., pm 이 있다.
일반적인 매칭에서는 어떤 위치 k에 대해 p1 = tk, p2 = t(k+1), ..., pm = t(k+m-1) 이면 P가 T의 위치 k에서 매칭된다고 한다. 이런 매칭은 Knuth-Morris-Pratt 알고리즘으로 찾을 수 있다.
이번에는 조금 더 어려운 매칭을 정의한다. P가 T의 위치 k에서 매칭된다는 것은 다음 조건을 만족하는 인덱스 k = a0 < a1 < ... < am 이 존재한다는 뜻이다.
- 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
즉, 텍스트를 연속한 비어 있지 않은 그룹들로 나누었을 때, 각 그룹의 합이 차례대로 패턴의 원소와 같아야 한다.
매칭의 개수는 P가 T의 서로 다른 시작 위치 k에서 매칭되는 경우의 수이다.
텍스트 T와 두 패턴 P1, P2가 주어질 때 다음 네 값을 구하시오.
- P1이 T에서 매칭되는 개수
- P2가 T에서 매칭되는 개수
- P1 · x · P2가 T에서 매칭되는 개수를 최대로 만드는 가장 작은 양의 정수 x. 여기서 x는 길이 1인 수열로 보고, ·는 수열의 이어 붙이기를 뜻한다.
- 3에서 구한 x를 사용했을 때 P1 · x · P2가 T에서 매칭되는 개수
입력
첫째 줄에 테스트 케이스의 개수 C가 주어진다. 각 테스트 케이스는 빈 줄로 구분될 수 있다.
각 테스트 케이스는 여섯 줄로 구성된다.
첫째 줄에는 텍스트의 길이 N이 주어진다.
둘째 줄에는 텍스트의 원소 N개가 주어진다.
셋째 줄에는 첫 번째 패턴의 길이 M1이 주어진다.
넷째 줄에는 첫 번째 패턴의 원소 M1개가 주어진다.
다섯째 줄에는 두 번째 패턴의 길이 M2가 주어진다.
여섯째 줄에는 두 번째 패턴의 원소 M2개가 주어진다.
N <= 11 * 10^6, M1, M2 <= 2 * 10^6 이다. 한 테스트 케이스에서 T, P1, P2에 포함된 모든 원소의 합은 22 * 10^6을 넘지 않는다.
출력
각 테스트 케이스마다 한 줄에 네 값을 문제에서 요구한 순서대로 공백으로 구분해 출력한다.
힌트
보이는 테스트에서 첫 번째 패턴은 텍스트의 위치 1, 2, 7, 8, 9, 10에서 매칭된다.
두 번째 패턴은 위치 1, 2, 3, 7, 8, 9, 10, 11에서 매칭된다.
수열 1, 1, 2, 48, 1, 1, 1은 텍스트의 위치 1, 2에서 매칭된다.
1 <= x < 47이면 수열 1, 1, 2, x, 1, 1, 1은 어디에서도 매칭되지 않는다.
수열 1, 1, 2, 47, 1, 1, 1은 텍스트의 위치 2에서만 매칭된다.
x > 48일 때는 세 곳에서 매칭되는 수열 1, 1, 2, x, 1, 1, 1이 없다.