동시 출현 검색
시간 제한2초메모리 제한512 MB
여러 테스트마다 긴 문자열에서 주어진 k개의 키 문자를 모두 포함하는 가장 짧은 부분 문자열을 모두 찾아 개수와 가장 왼쪽 부분 문자열을 출력한다.
문제
WWW에는 방대한 양의 정보가 쌓여 있다. 잘 정리되어 있지는 않지만, 사용자는 이미 확립되어 있으나 다소 시대에 뒤떨어진 백과사전을 찾는 대신, WWW를 최신 정보의 무한한 원천으로 삼아 탐색할 수 있다. 하지만 키워드 검색 알고리즘을 더 깊이 이해하면 WWW를 한층 더 활용할 수 있다.
예를 들어 Windows와 UNIX의 최근 비교에 대한 정보를 얻고 싶다면, 키워드 "Windows"와 "UNIX"를 모두 포함하면서 서로 가까이 있는 텍스트를 뽑아내어, 방대한 웹 텍스트 더미에서 관련 있는 서술을 얻기를 기대할 수 있다.
여기서는 이 동시 출현 키워드 검색 문제를 단순화한 버전을 다룬다. 텍스트와 키워드는 각각 문자열과 키 문자로 대체된다. 길이 n(1 ≤ n ≤ 1, 000, 000)인 문자열 S와 k개의 서로 다른 키 문자로 이루어진 집합 K = {a1, ..., ak}(1 ≤ k ≤ 50)가 주어진다. S의 부분 문자열 중 키 문자 a1, ..., ak를 모두 포함하는 가장 짧은 부분 문자열을 모두 찾아라.
입력
입력은 출력 가능한 문자(16진수 ASCII 코드 21부터 7E까지)와 줄바꿈 문자로만 이루어진 텍스트 파일이다. 공백이나 탭 같은 화이트스페이스는 입력에 나타나지 않는다.
텍스트는 위에서 설명한 최단 문자열 검색 문제가 연속된 형태이다. 각 문제는 문자열 Si와 키 문자 집합 Ki(i = 1, 2, ..., p)로 이루어진다. 각 Si와 Ki 뒤에는 빈 줄이 온다. 다만 문자열에서 연속한 줄 사이의 줄바꿈은 무시한다. 즉, 줄바꿈은 문자열의 일부가 아니다. 여러 기술적인 이유로 모든 줄은 최대 72자로 이루어진다. 각 키 문자 집합은 한 줄로 주어진다. 입력은 연속한 빈 줄로 끝난다. p는 명시적으로 주어지지 않는다.
출력
p개의 문제를 모두 풀고 그 답을 순서대로 출력해야 한다. 다만 한 문제에서 최단 부분 문자열이 여러 개 발견되더라도 그것을 전부 출력할 필요는 없다. 발견된 부분 문자열이 너무 많아 모두 확인하기 어려울 수 있기 때문이다. 대신 그 부분 문자열의 개수와 대표 하나만 요구된다. 즉, 각 문제 i에 대해 최단 부분 문자열의 개수를 출력한 뒤, 가장 앞쪽(가장 왼쪽)의 최단 부분 문자열 si1을 다음 형식에 따라 출력한다.
the number of the shortest substrings for the i-th problem
empty line
the first line of si1
the second line of si1
...
the last line of si1
empty line for the substring termination
여기서 최단 부분 문자열 si1의 각 줄은 마지막 줄을 제외하고 정확히 72자로 이루어져야 하며, 마지막 줄(부분 문자열이 72자 이하인 경우에는 물론 그 유일한 줄)은 72자를 넘지 않아야 한다.
어떤 문제에 대해 그러한 부분 문자열이 없으면 출력은 0과 빈 줄이 된다. 종료할 부분 문자열이 없으므로 연속한 빈 줄을 더 출력해서는 안 된다.