lcstring

For subtask $1$, enumerate every interval of $A$ and directly check whether it also appears in $B$.

For the full problem, let $D_{i,j}$ be the maximum length of a common interval ending at both $A_i$ and $B_j$. If the two elements match, extend the common interval ending at the preceding elements. Otherwise, no nonempty common interval ends at both positions. Thus

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

The answer length is the maximum of all $D_{i,j}$. When this maximum increases, also store its ending position in $A$. The corresponding $K$ elements ending at that position form an answer.

Only the previous DP row is needed, so each case takes $O(NM)$ time. The DP uses $O(M)$ space, and the total space including the input sequences is $O(N+M)$.

Solution written by GPT6