Time Limit: 10s
Memory Limit: 128MB
편집 거리란 특정 영단어 x를 y로 변환하려고 할 때 몇 번의 연산을 적용 해야지 x가 y로 변환이 되는가를 나타내는 척도이다. 이때 x를 구성하는 하나의 알파벳에 대해서만 삽입, 삭제, 혹은 수정 중 하나의 연산을 적용했을 때 y로 변환되면 이 둘의 편집 거리는 1이다. 예를 들어 dig라는 dog 로 변환하기 위해서는 i를 o로 수정하는 한 번의 단계를 거치면 되기 때문에 두 단어 사이의 편집 거리가 1이 된다.
주어진 영영 사전에 대해서 가장 긴 "편집 단계 사다리"를 찾는 프로그램을 작성하라.
(알파벳 순서로 정렬된 단어 시퀀스 w1, w2, ..., wn에 대하여 시퀀스 안의 모든 wi와 wi+1에 대해서 편집거리가 1인 경우 이를 편집 단계 사다리라고 정의한다.)
사전식 순서로 정렬된 소문자 단어들의 집합
가장 긴 편집 단계 사다리 안에 포함된 단어의 개수 (정수)
cat dig dog fig fin fine fog log wine
5
dig, fig, fin, fine, wine