| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 28 | 11 | 11 | 61.111% |
비어 있는 두 문자열 $A$, $B$가 있다. 아래의 세 가지 종류의 쿼리를 순서대로 처리하는 프로그램을 작성하여라.
1 c x: 문자열 $A$의 맨 뒤에 문자 $c$를 $x$번 이어 붙인다.2 c x: 문자열 $B$의 맨 뒤에 문자 $c$를 $x$번 이어 붙인다.3: 현재 문자열 $A$와 $B$의 최장 공통 연속 부분문자열(Longest Common Substring)의 길이를 출력한다.모든 쿼리를 처리하면서, 3번 쿼리가 주어질 때마다 해당 시점의 답을 출력하여라.
첫째 줄에 쿼리의 개수 $Q$가 주어진다. $(1\le Q\le 5\,000)$
다음 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. 각 쿼리는 다음 세 가지 형식 중 하나이다. $c$는 알파벳 소문자이며 $x$는 양의 정수이다. $(1\le x\le 100\, 000)$
1 c x2 c x33번 쿼리가 최소 한 번 이상 주어짐이 보장된다.
3번 쿼리가 주어질 때마다 현재 문자열 $A$와 $B$의 최장 공통 연속 부분문자열의 길이를 한 줄에 하나씩 출력한다.
5 3 1 a 1 3 2 a 1 3
0 0 1
9 1 b 2 3 1 c 3 3 2 c 2 3 2 z 1 2 c 1 3
0 0 2 2
13 1 a 3 2 a 1 3 2 b 3 1 b 2 3 1 b 1 2 c 2 3 1 c 2 3 1 c 1 3
1 3 4 6 6
어떤 문자열의 연속 부분문자열(substring)이란, 문자열에서 연속한 구간을 선택하여 얻는 문자열을 의미한다. 예를 들어 문자열 abcde의 연속 부분문자열에는 a, bc, cde, abcde 등이 있으며, ace는 연속 부분문자열이 아니다.
두 문자열의 최장 공통 연속 부분문자열이란, 두 문자열의 공통된 연속 부분문자열 중 길이가 가장 긴 것을 의미한다. 예를 들어 $A=$ aaabb, $B=$ caaab 라면 두 문자열의 최장 공통 연속 부분문자열은 aaab이며, 그 길이는 $4$이다.