cho.sh전문 검색
각 질의에 대해 길이 1과 2인 부분 문자열 집합이 질의의 집합을 모두 포함하면서 질의 문자열 자체는 포함하지 않는 가장 짧은 문자열의 길이를 구한다.
보통7문자열그래프최단 경로완전 탐색아직 제출이 없습니다시간 제한8초메모리 제한512 MB문제
어떤 퀴즈 사이트는 사용자가 문제 텍스트를 직접 등록하고, 원하는 문자열로 문제 텍스트를 검색한다. 이 검색 기능은 바이그램 검색 방식을 쓴다.
바이그램 검색은 전처리와 검색, 두 단계로 나뉜다.
전처리: 각 문제 텍스트에서 길이가 1 또는 2인 모든 부분 문자열을 모아 집합을 미리 구해 둔다.
검색: 질의 문자열에서도 같은 방법으로 집합을 구한 뒤, 미리 구해 둔 집합이 질의의 집합을 모두 포함하는 문제 텍스트를 찾는다.
기능을 공개하고 얼마 지나지 않아 한 사용자가 결함을 발견했다. 검색 결과에 질의 문자열을 그대로 포함하지 않는 문제 텍스트가 섞여 나올 때가 있다. 관리자는 원인을 확인하려 한다. 질의가 주어지면 바이그램 검색에는 걸리지만 질의를 부분 문자열로 포함하지 않는 문제 텍스트 중 가장 짧은 것의 길이를 구하라. 문제 텍스트는 영문 대문자와 소문자로 이루어진, 비어 있지 않은 문자열이다.
입력
입력은 여러 개의 데이터로 이루어진다. 각 줄에 검색 질의가 하나씩 주어진다. 마지막 줄에는 해시 기호 하나만 있는 줄 #이 주어지며, 이 줄은 처리하지 않는다.
검색 질의의 길이는 1 이상 1000 이하이고, 영문 대문자와 소문자로만 이루어진다. 문제 텍스트와 질의는 대문자와 소문자를 구분한다.
출력
각 검색 질의마다 결함을 일으키는 문제 텍스트의 최소 길이를 한 줄에 출력한다. 그런 문제 텍스트가 없으면 No Results를 출력한다.
힌트
문제 텍스트가 CloneQMAC이면 전처리 단계에서 구한 집합은 {C, Cl, l, lo, o, on, n, ne, e, eQ, Q, QM, M, MA, A, AC}이다.
질의가 QMAClone이면 검색 단계에서 구한 집합은 {Q, QM, M, MA, A, AC, C, Cl, l, lo, o, on, n, ne, e}이다.
첫 번째 집합이 두 번째 집합의 원소를 모두 포함하므로 질의 QMAClone의 검색 결과에 CloneQMAC이 들어간다. 그런데 CloneQMAC에는 QMAClone이 부분 문자열로 들어 있지 않다. 길이가 9보다 짧은 그런 텍스트는 없으므로 이 질의의 답은 9다.