cho.sh연구초미니
문제 설명
시간 제한
메모리 제한
cho.sh시간 제한
메모리 제한
시간 제한
30초
메모리 제한
1536 MB
양의 정수로 이루어진 텍스트 수열 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 이 존재한다는 뜻이다.
즉, 텍스트를 연속한 비어 있지 않은 그룹들로 나누었을 때, 각 그룹의 합이 차례대로 패턴의 원소와 같아야 한다.
매칭의 개수는 P가 T의 서로 다른 시작 위치 k에서 매칭되는 경우의 수이다.
텍스트 T와 두 패턴 P1, P2가 주어질 때 다음 네 값을 구하시오.
첫째 줄에 테스트 케이스의 개수 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이 없다.