시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
30 초 | 1536 MB | 54 | 13 | 8 | 27.586% |
다음과 같이 양수로 이루어진 두 수열이 있다. T=t1,t2,...,tn (텍스트), P=p1,p2,...,pm(패턴).
매칭이란 p1=tk, p2=tk+1, ..., pm=tk+m-1일때, "P는 k에서 T와 매칭된다" 라고 한다. 이러한 매칭은 Knuth-Morris-Pratt 알고리즘으로 찾을 수 있다.
매칭은 쉬우니깐, 조금 더 어려운 매칭을 생각해보자. P가 k에서 T와 매췽된다는 말은 아래와 같은 조건을 만족하는 수열 k=a0 < a1 < ... < am이 있을 때이다.
ta0 + ta0+1 + ... + ta1-1 = p1
ta1 + ta1+1 + ... + ta2-1 = p2
...
tam-1 + tam-1+1 + ... + tam-1 = pm
매췽은 먼저 텍스트를 그룹짓고 그룹 내의 연속된 합을 구한 다음에, 패턴을 찾는 것이다.
예를 들어, T=1,2,1,1,3,2이고, P=3,2일 때를 생각해보자. 이때는 2개의 매췽이 있는데, k=1 (a1=3, a2=5) 일때와 k=5 (a1=6, a2=7)일 때 이다.
매췽의 개수는 P가 k에서 T와 매췽된때 k의 서로 다른 개수이다.
텍스트 P와 두 개의 패턴 P1, P2가 주어졌을 때, 다음을 구하시오.
1. T와 P1의 매췽의 개수
2. T와 P2의 매췽의 개수
3. T와 P1 ⋅ n ⋅ P2의 매췽의 개수를 최대로 하는 가장 작은 양의 정수 n (⋅는 수열을 합치는 것이다)
4. T와 P1 ⋅ n ⋅ P2의 개수 (여기서 n은 3에서 구한 n이다)
첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 빈 줄로 구분된다.
각 테스트 케이스는 다음과 같이 여섯 줄로 구성되어 있다.
첫째 줄에는 텍스트의 길이 N이 주어진다.
둘째 줄에는 텍스트의 원소 N개가 주어진다.
셋째 줄에는 첫 번째 패턴의 길이 M1이 주어진다.
넷째 줄에는 첫 번째 패턴의 원소 M1개가 주어진다.
다섯째 줄에는 두 번째 패턴의 길이 M2이 주어진다.
여섯째 줄에는 두 번째 패턴의 원소 M2개가 주어진다.
N<=5000, M1,M2<=600, T와 P1, P2에 포함되어 있는 모든 원소를 합한 값은 11,000을 넘지 않는다.
각 테스트케이스이 대해 한 줄에 문제에서 구하라 했던 순서대로 빈 칸을 사이에 두고 출력한다.
1 13 1 1 1 1 1 47 1 1 1 1 1 1 1 3 1 1 2 3 1 1 1
6 8 48 2
첫 번째 패턴은 텍스트의 위치 1, 2, 7, 8, 9, 10에서 매췽된다.
두 번째 패턴은 1, 2, 3, 7, 8, 9, 10, 11에서 매췽된다.
"1,1,2,48,1,1,1"은 텍스트의 위치 1, 2에서 매췽된다.
n이 1<=n<47 일 때, "1,1,2,n,1,1,1"은 어느 곳에서도 매췽되지 않는다.
"1,1,2,47,1,1,1"은 텍스트의 위치 2에서만 매췽된다.
n>48일 때, 세 곳에서 매췽되는 "1,1,2,n,1,1,1"은 없다.