문제 13
세종대왕돈까스
세종대왕돈까스는 "세종대 왕돈까스"일까 "세종대왕 돈까스"일까?
알파벳 소문자로 이루어진 문자열 $S$가 주어질 때, 문자열을 길이가 $1$ 이상인 두 문자열로 분할하는 서로 다른 방법은 몇 가지일까?
예를 들어, aaaa를 두 문자열로 분할하는 서로 다른 방법은 a aaa로 나누는 방법과 aa aa로 나누는 방법으로 총 $2$가지이다.
이때 a aaa로 나누는 방법과 aaa a로 나누는 방법처럼 순서만 다른 경우는 동일하다고 가정한다.
입력
첫 번째 줄에 테스트케이스의 개수를 의미하는 정수 $T$가 주어진다. $(1 \le T \le 1\,000)$
두 번째 줄부터 $T$개의 줄에 걸쳐 문자열 $S$가 주어진다. $(2 \le \lvert S \rvert \le 20\,000)$
출력
각 테스트케이스마다 문자열을 두 개의 비어 있지 않은 문자열로 나누는 서로 다른 방법의 수를 한 줄에 하나씩 출력한다.
예제 입력 1
3 aaaa abcd ababab
예제 출력 1
2 3 4
공식 해설
중복되는 절단 위치는 서로 짝을 이룬다
문자열의 길이를 $n$이라 하자. 비어 있지 않은 두 조각으로 나누는 절단 위치는 $n-1$개이다.
앞 조각의 길이가 $i$인 분할과 다른 위치의 분할이 같으려면 두 조각의 순서가 뒤바뀌어야 한다. 따라서 상대 절단 위치는 반드시 $n-i$이다. 두 위치가 같은 조각들을 만들 조건은 길이 $i$인 접두사와 접미사가 같고, 길이 $n-i$인 접두사와 접미사도 같은 것이다.
이처럼 문자열의 접두사와 접미사가 일치하는 길이를 표시해 두면, $1\le i<n/2$에서 $i$와 $n-i$가 모두 표시된 경우마다 답을 $1$ 줄이면 된다. 중복 상대가 유일하므로 한 쌍을 한 번만 제외한다. $i=n/2$는 같은 절단 위치라서 제외하지 않는다.
접두사 함수로 일치 길이 구하기
문자열의 인덱스는 $0$부터 $n-1$까지로 둔다. KMP의 접두사 함수 $\pi_i$는 $S_0\cdots S_i$의 접두사이면서 접미사인 문자열 중 자기 자신을 제외한 최장 길이이다. 이전 일치 길이에서 다음 문자가 다르면 $j\leftarrow\pi_{j-1}$로 돌아가고, 같으면 길이를 하나 늘려 전처리한다.
전체 문자열의 가장 긴 일치 길이는 $\pi_{n-1}$이다. 여기에서 시작해 $j>0$인 동안 $j$를 표시하고 $j\leftarrow\pi_{j-1}$을 반복하면 모든 일치 길이를 얻는다. 긴 일치 부분의 더 짧은 접두사·접미사 일치가 바로 다음 후보이기 때문이다.
예를 들어 aaaa에서는 세 절단 위치 중 길이 $1$과 $3$에서 자른 두 분할이 중복되므로 답은 $3-1=2$이다.
테스트케이스당 시간복잡도와 공간복잡도는 $O(n)$이다.
구현 · 언어별 풀이
C++ 구현
접두사 함수는 vector<int>, 일치하는 길이의 표시는 vector<char>로 저장한다. 접두사 함수에서 길이를 되돌릴 때는 j > 0을 확인한 뒤 pi[j - 1]을 읽는다. 절단 위치는 가운데를 제외한 2 * i < n만 검사하여 같은 쌍을 두 번 빼지 않는다.
C 구현
char 배열과 int 접두사 배열로 KMP를 구현한다. border 길이는 접두사 배열을 따라 내려가며 표시한다. 같은 분할을 두 번 제외하지 않도록 $i$와 $n-i$ 중 작은 쪽만 검사하고 정중앙은 중복 분할이 아니다.
접두사 배열의 초깃값은 모두 $0$으로 둔다.
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) j = pi[j - 1];
if (s[i] == s[j]) j++;
pi[i] = j;
}Python 구현
문자열과 접두사 길이 리스트를 사용한다. 실패할 때 $j$를 한 칸씩 줄이지 않고 pi[j - 1]로 이동한다. border를 불리언 배열에 표시하면 각 분할의 중복 여부를 상수 시간에 확인한다.
접두사 배열의 초깃값은 모두 $0$으로 둔다.
pi = [0] * len(s)
for i in range(1, len(s)):
j = pi[i - 1]
while j and s[i] != s[j]:
j = pi[j - 1]
if s[i] == s[j]:
j += 1
pi[i] = jJava 구현
charAt()과 int[] pi, boolean[] border로 처리한다. $j>0$일 때만 pi[j - 1]을 읽는다. $i$와 $n-i$가 모두 border인 경우를 세되 2*i < n인 쪽만 제외한다.
접두사 배열의 초깃값은 모두 $0$으로 둔다.
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s.charAt(i) != s.charAt(j)) j = pi[j - 1];
if (s.charAt(i) == s.charAt(j)) j++;
pi[i] = j;
}Rust 구현
as_bytes()와 Vec<usize> 접두사 배열을 사용한다. j > 0을 확인한 뒤 pi[j - 1]로 돌아간다. border 체인을 표시하고 2*i < n인 분할만 중복으로 제외한다.
접두사 배열의 초깃값은 모두 $0$으로 둔다.
let s = s.as_bytes();
let mut pi = vec![0; s.len()];
for i in 1..s.len() {
let mut j = pi[i - 1];
while j > 0 && s[i] != s[j] { j = pi[j - 1]; }
if s[i] == s[j] { j += 1; }
pi[i] = j;
}JavaScript 구현
접두사 길이는 Int32Array(s.length), border 표시는 Uint8Array(s.length)로 둔다. 문자열은 소문자 ASCII이므로 s[i]로 비교한다. 불일치 시 j = pi[j - 1]로 이동하고 일치하면 $1$ 늘린다.
중복을 셀 때는 2 * i < n인 위치만 확인한다. 테스트케이스마다 접두사 배열과 border 배열을 초기화한다.