편집 거리 — NYPC 2025

두 문자열 $A$ 와 $B$ 의 편집 거리는, 문자열 $A$ 를 $B$ 로 바꾸기 위해 적용해야 하는 편집 작업의 최소 횟수로 정의된다. 가능한 편집 작업은 아래의 $3$ 가지가 있다:

삽입: 현재 문자열의 임의의 위치에 글자를 하나 삽입한다.
삭제: 현재 문자열의 임의의 위치의 글자를 하나 삭제한다.
변경: 현재 문자열의 임의의 위치의 글자 하나를 다른 글자로 바꾼다.

두 문자열 aba와 abba의 경우, aba의 첫 글자와 두 번째 글자 사이에 b를 삽입하면 abba가 되므로 편집 거리는 $1$ 이다. 또, 두 문자열 aba와 acaa의 경우, aba의 문자 b를 c로 변경하고, 마지막 문자 a 뒤에 새로운 문자 a를 삽입하면 acaa가 되므로 편집 거리는 $2$ 가 된다.

임의의 문자열 $A$ , $B$ 에 대해, $A$ 와 $B$ 의 편집 거리와 $B$ 와 $A$ 의 편집 거리는 같음에 유의하라.

주어진 문자열 $P$ 와 $T$ 에 대해서, $T$ 의 모든 연속이고 길이가 $1$ 이상인 부분문자열과 $P$ 의 편집 거리들 중, 그 값이 각각 $0, 1, \ldots, K$ 인 경우의 수를 구하는 프로그램을 작성하라.

입력 형식

첫 줄에 문자열 $T$ 의 길이 $N$ , 문자열 $P$ 의 길이 $M$ , 편집 거리의 제한을 나타내는 정수 $K$ 가 공백으로 구분되어 주어진다. ( $1 \le N \le 100\,000;$ $1 \le M \le 1\,000;$ $0 \le K \le M$ ; 이 문제는 입력 제한이 일반적이지 않으므로 주의하라; 아래 채점 방식 부분에 추가적인 정보가 있다)

그다음 줄에 길이 $N$ 의 문자열 $T$ 가 주어진다.

그다음 줄에 길이 $M$ 의 문자열 $P$ 가 주어진다.

주어지는 문자열 $T$ 와 $P$ 는 모두 영어 알파벳 소문자로만 구성되어 있다.

출력 형식

첫 줄부터 $K + 1$ 개의 줄에 걸쳐 정답을 출력한다. $i + 1$ 번째 줄에는 $P$ 와의 편집 거리가 정확하게 $i$ 인 경우의 수를 출력한다.

예제

입력

7 3 1 abbabaa aba

출력

1 10

예제 설명

편집 거리가 $0$ 인 경우는 $T$ 의 $4$ 번째 글자에서 시작하는 부분문자열 aba $1$ 개가 있다.

편집 거리가 $1$ 인 경우는 $T$ 의 $1$ 번째 글자에서 시작하는 부분문자열 ab, abb, abba가 있고, $2$ 번째 글자에서 시작하는 bba, $3$ 번째 글자에서 시작하는 ba, baba, $4$ 번째 글자에서 시작하는 ab, abaa, $5$ 번째 글자에서 시작하는 ba, 마지막으로, $6$ 번째 글자에서 시작하는 aa가 있어, 모두 $10$ 개이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다. 입력 케이스 종류들 중 하나가 다른 모든 종류를 포함하는 경우가 없음에 주의하라.

종류 1: 8점

$N \le 1000;$ $M \le 100$

종류 2: 12점

$N \le 3000;$ $K \le 20$

종류 3: 35점

$N \le 5000$

종류 4: 11점

$K \le 2$

종류 5: 34점

$K \le 20$

해설

어떤 문자열 $S$ 에 대해서,

$S[i]$ : $S$ 의 $i$ 번째 문자
$S[i\dots]$ : $i$ 번째 문자부터 시작하는 접미사
$S[\dots i]$ : 길이 $i$ 의 접두사
$S[i\dots j]$ : $i$ 번째 문자부터 $j$ 번째 문자까지의 연속 부분문자열

을 의미한다고 합시다.

문제를 풀기 위해서는, 문자열 $T[i\dots]$ 와 문자열 $P$ 의 편집 거리를 계산해야 합니다. $DP[i][j]$ 를 $T[\dots i]$ 와 $P[\dots j]$ 의 최소 편집 거리라고 정의합니다.

$i = 0$ 인 경우, $DP[i][j] = j$
$j = 0$ 인 경우, $DP[i][j] = i$
그 외의 경우 $DP[i][j] = \min (DP[i-1][j] + 1, DP[i][j-1] + 1, DP[i-1][j-1] + \delta_{i,j})$

여기서 $T[i] = P[j]$ 이면 $\delta_{i,j} = 0$ 이고, 아니면 $\delta_{i,j} = 1$ 입니다.

전체 문자열 $T$ 에 대해 $T[1\dots], T[2\dots], \dots$ 와 $P$ 의 편집 거리를 위의 DP를 이용하여 각각 계산합니다.

각 접미사 $T[i\dots]$ 에 대해 DP의 마지막 열 $DP[\ast][M]$ 을 확인하면, $T[i\dots]$ 의 접두사들과 $P$ 의 편집 거리가 $K$ 이하인지 판별할 수 있습니다.

이를 통해, $T$ 의 연속된 부분문자열 중에서 $P$ 와의 편집 거리가 $K$ 이하인 것의 개수를 구할 수 있습니다. 이때, 두 문자열의 길이 차이가 $K$ 보다 크면 편집 거리는 항상 $K$ 를 초과하므로, 최대 길이가 $M + K$ 인 문자열들만 고려하면 충분합니다. 각 접미사마다 독립적으로 DP를 수행하면, 총 시간복잡도는 $O(NM^2)$ 가 되어 subtask1을 해결할 수 있습니다.

DP 테이블을 관찰하면 $\lvert i - j \rvert > K$ 인 칸은 계산할 필요가 없습니다. 이 구간에서는 최소 $K+1$ 회의 삽입 또는 삭제가 필요하기 때문입니다. 따라서 $\lvert i - j \rvert \le K$ 인 셀들만 계산해도 충분하며, 이 영역의 칸들만 계산하면 $O(NMK)$ 에 문제를 해결할 수 있어 subtask2를 해결할 수 있습니다.

DP 전체를 저장하지 않고, 인접 셀 간의 차이를 나타내는 배열을 관리합시다. $D$ 가 DP 배열에서 인접한 셀들과의 차이를 저장하는 배열이라고 합시다. $T[i\dots X]$ 와 $T[i+1\dots X]$ 에 대해 수행된 DP배열의 D배열을 비교할 때, $D$ 값이 변하는 위치는 최대 $O(M)$ 개입니다. 따라서 $T$ 의 인덱스를 한 칸 옮길 때마다 $O(M)$ 개의 위치만 업데이트하면 충분합니다. 각 단계에서 $D$ 배열을 통해 DP 값을 복원할 수 있으므로, 전체 시간복잡도는 $O(NM)$ 입니다. 이 방법으로 subtask 3을 해결할 수 있습니다.

DP 테이블을 대각선 단위로 관찰하면, 같은 대각선( $i - j = s$ ) 위의 값들은 항상 단조 증가하며, 증가 시 $1$ 씩만 증가한다는 사실을 알 수 있습니다. 따라서 각 대각선별로 “값이 $k - 1$ 에서 $k$ 로 증가하는 지점”만 추적하면 DP 전체를 직접 계산하지 않아도 됩니다.

$D(i,j) = k-1$ 인 마지막 칸을 $(i_s^{k-1}, j_s^{k-1})$ 라고 하면, $(i_s^{k}, j_s^{k})$ 는 다음 세 경우 중 하나에서 얻을 수 있습니다.

$(i_s^{k-1} + 1, j_s^{k-1} + 1)$ 에서 값 증가 없이 대각선 타고 이동
$(i_{s-1}^{k-1} + 1, j_s^{k-1})$ 에서 값 증가 없이 대각선 타고 이동
$(i_{s+1}^{k-1}, j_{s+1}^{k-1}+1)$ 에서 값 증가 없이 대각선 타고 이동

$T[i\dots]$ 와 $P[j\dots]$ 의 접두사가 일치하는 동안 대각선 방향으로 계속 확장할 수 있습니다. 이는 곧 Longest Common Prefix (LCP) 를 구하는 것과 같습니다. LCP는 Suffix Array와 LCP 배열, 또는 Sparse Table을 이용하면 쿼리당 $O(1)$ 에 계산할 수 있습니다. 각 $T[i\dots]$ 마다 $O(K^2)$ 가 걸리므로, 전체 시간복잡도는 $O(NK^2)$ 입니다. 이 방법으로 subtask 4와 subtask 5를 해결할 수 있습니다.

$O(NM)$ 방법과 $O(NK^2)$ 방법을 결합하면, 전체 문제를 효율적으로 해결할 수 있습니다.

Challenge: 모든 서브태스크를 한번에 해결할 수 있는 $O(NK)$ 풀이도 존재합니다. 어떻게 하면 될까요?