가장 긴 공통 부분 문자열
시간 제한1초메모리 제한1024 MB
처음 M개 소문자로 이루어진 N개의 문자열이 주어질 때, 서로 다른 K개 문자를 순서를 지켜 뽑아 만든 문자열 P가 가장 많은 문자열의 부분열이 되는 경우를 찾아 그 개수, 사전순으로 가장 작은 P, 그리고 그러한 P의 서로 다른 개수를 구한다.
문제
N개의 문자열 S1, S2, ..., SN이 주어진다. 각 문자열은 처음 M개의 소문자 라틴 문자로 구성되며, 길이는 L보다 작다. 몇몇 문자열 Si에서 각각 K개의 서로 다른 문자를 골라(반드시 연속일 필요는 없다) 원래 순서를 유지한 채 새로운 문자열 Pi를 만든다. 모든 Pi가 같아지도록 문자열 Si를 고를 수 있는 최대 개수는 얼마인가? 이 질문에 답하는 프로그램 long을 작성하라.
입력
첫째 줄에 N, M, K가 공백으로 구분되어 주어진다. 다음 줄부터는 주어진 문자열이 한 줄에 하나씩 주어진다.
출력
첫째 줄에 같은 새 문자열들의 최대 길이를 출력한다. 둘째 줄에 그 새 문자열 중 사전순으로 가장 작은 것을 출력한다. 셋째 줄에 가능한 서로 다른 새 문자열들의 개수를 출력한다. 답이 없으면 0을 한 줄에 출력한다.
힌트
순서쌍 cb가 등장하는 문자열의 최대 개수는 4이다. 또 다른 순서쌍 cd도 주어진 문자열 4개에 등장하지만, cd는 사전순으로 cb보다 뒤에 온다.