항체 중쇄 군집화

시간 제한2초메모리 제한256 MB

요약

n개 항체 사슬을 앞 k글자나 뒤 k글자가 같은 묶음으로 나누어 묶음 수를 최소화합니다.

문제

생물학자들이 바이러스성 질병의 치료제를 찾고 있다. 여러 기원의 항체를 바이러스 항원에 시험해 본 뒤, 실험에서 가장 잘 작동한 항체 $n$ 개를 골랐다.

항체는 저마다 중쇄로 구분한다. 중쇄는 아미노산을 늘어놓은 서열이고, 아미노산 하나는 영어 대문자 하나로 적는다.

항체의 집합이 다음 두 조건 중 적어도 하나를 만족하면 유사 군집이다.

항체 하나로만 이루어진 집합은 언제나 유사 군집이다.

이후 연구를 간단히 하려고 생물학자들은 항체 $n$ 개를 유사 군집으로 나누려 한다. 항체는 모두 정확히 한 군집에만 속해야 한다. 군집이 최소 몇 개 필요한지 구하라.

첫째 줄에 중쇄의 개수 $n$ 과 일치해야 하는 아미노산 서열의 길이 $k$ 가 주어진다 ( $1 \le n \le 5000$ , $1 \le k \le 550$ ).

다음 $n$ 개 줄에는 항체의 중쇄가 한 줄에 하나씩 주어진다. 아미노산은 모두 영어 대문자이고, 중쇄의 길이는 $k$ 이상 $550$ 이하이다.

항체 $n$ 개를 나누는 데 필요한 유사 군집 개수의 최솟값을 정수 하나로 출력한다.