연속 구간 찾기
ABXCD와 AYBCD에서는 CD가 두 문자열 모두에 연속해서 나타난다. 더 긴 공통 연속 구간은 없으므로 최장 길이는 2다. 두 문자열에 공통으로 뽑을 수 있는 ABCD와는 다른 결과다.
일치가 끊기면 초기화
두 문자열의 특정 위치에서 끝나는 공통 구간 길이를 생각할 수 있다. 현재 문자가 같으면 바로 이전 두 위치에서 끝난 길이에 1을 더한다. 다르면 그 위치에서 끝나는 길이는 0으로 돌아간다.
표에서 찾는 값
이 방식의 동적 계획법에서는 마지막 칸만 답으로 읽지 않는다. 공통 구간이 문자열 중간에서 끝날 수 있으므로 모든 칸에서 가장 큰 길이를 찾아야 한다. 원래 문자열의 끝까지 이어지는 조건은 없다.
구간 복원과 동률
최대 길이와 그 구간의 끝 위치를 저장하면 시작 위치도 계산할 수 있다. 같은 최대 길이를 가진 공통 구간이 여럿이면 하나만 반환할지 모두 반환할지 정한다. 길이가 0인 경우와 빈 문자열 입력도 처리 범위에 포함한다.