최장 공통 부분 문자열

서브태스크 $1$에서는 $A$의 모든 구간을 열거하고 각 구간이 $B$에도 나타나는지 직접 확인할 수 있다.

전체 문제에서는 $D_{i,j}$를 $A_i$와 $B_j$에서 함께 끝나는 공통 구간의 최대 길이라고 하자. 두 원소가 같으면 이전 두 원소에서 끝나는 공통 구간을 연장할 수 있고, 다르면 그 위치에서 끝나는 공통 구간이 없다. 따라서

$$D_{i,j}=\begin{cases}D_{i-1,j-1}+1,&A_i=B_j,\\0,&A_i\ne B_j.\end{cases}$$

이다. 모든 $D_{i,j}$의 최댓값이 답의 길이이다. 최댓값을 갱신할 때 $A$에서 끝나는 위치도 저장하면 그 위치부터 거꾸로 $K$개 원소를 찾아 답을 출력할 수 있다.

현재 행은 이전 행만 필요하므로 한 케이스의 시간 복잡도는 $O(NM)$이다. DP에는 $O(M)$의 공간을 쓰며, 입력 수열까지 포함한 전체 공간 복잡도는 $O(N+M)$이다.

Solution written by GPT6