코드 절도
시간 제한1초메모리 제한128 MB
두 소스의 줄을 정규화한 뒤 연속으로 겹치는 가장 긴 줄 구간을 찾아 그 길이와 해당 파일 이름을 출력한다.
문제
새로운 소스 코드가 회사 저장소에 올라올 때마다, 그 코드가 인터넷에 공개된 오픈 소스를 그대로 베낀 것은 아닌지 자동으로 검사하는 모니터링 시스템을 만들려고 한다.
시스템은 새로 제출된 소스 코드 전체를, 알려져 있는 모든 오픈 소스 파일과 하나씩 비교한다. 각 오픈 소스 파일에 대해, 제출된 소스와 연속으로 겹치는 줄이 가장 길게 이어지는 구간의 길이를 구한다.
비교는 줄 단위로 이루어지며, 다음 규칙을 따른다.
- 빈 줄과 공백만으로 이루어진 줄은 비교 대상이 아니며, 줄 수에도 포함하지 않는다. (이런 줄은 없는 것으로 보고, 그 앞뒤의 의미 있는 줄들은 서로 인접한 것으로 취급한다.)
- 각 줄의 맨 앞과 맨 뒤에 있는 공백은 무시한다.
- 줄 가운데에 있는 연속된 공백은 공백 하나로 취급한다.
- 모든 비교는 대소문자를 구분하지 않는다.
두 소스를 위 규칙으로 정규화한 뒤, 양쪽 모두에서 연속으로 나타나는 가장 긴 줄 묶음의 길이가 그 파일과의 겹침 정도가 된다.
입력
첫째 줄에 알려져 있는 오픈 소스 파일의 개수 이 주어진다. ()
이어서 개의 오픈 소스 정보가 차례로 주어진다. 각 오픈 소스는 첫 줄에 파일 이름이 주어지고, 그 다음 줄부터 소스 코드의 내용이 이어진다. 소스 코드의 끝은 ***END*** 한 줄로 표시하며, 이 줄은 소스 코드의 일부가 아니다. 파일 이름은 공백을 포함하지 않고, 서로 중복되지 않으며, 길이는 최대 254글자이다.
모든 오픈 소스가 주어진 다음, 비교할 소스 코드가 주어진다. 이 소스 코드의 끝에도 ***END*** 한 줄이 주어진다.
모든 줄의 길이는 254글자 이하이고, 한 소스 코드는 10000줄 이하이다. 소스 코드와 파일 이름은 아스키 문자 32번부터 126번까지만 포함하며, 입력 전체의 길이는 글자를 넘지 않는다.
출력
제출된 소스와 가장 길게 연속으로 겹치는 줄의 수를 첫째 줄에 출력한다. (빈 줄은 세지 않는다.)
이어서 공백을 하나 출력한 뒤, 그 최대 길이를 달성하는 오픈 소스 파일의 이름을 출력한다. 해당하는 파일이 여러 개이면 입력에 주어진 순서대로 공백으로 구분하여 모두 출력한다.
겹치는 줄이 하나도 없으면 (최대 길이가 이면) 만 출력한다.