시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 150 | 34 | 23 | 20.000% |
홍준이는 문자열을 좋아합니다. 그래서 문자열과 관련된 여러 문제들을 고민하고 있습니다.
그 중 하나는 문자열 S가 주어졌을 때, 어떤 두 문자열 A와 B를 모두 포함하는 S의 연속 부분 문자열 중 가장 길이가 짧은 것을 구하는 문제입니다. 홍준이는 똑똑해서 이 문제를 금방 풀어버렸습니다. 그래서 한층 더 어려운 문제를 생각하였습니다. 두 문자열 A와 B가 질문 Q번 들어올 때에는 어떻게 빠르게 답을 구할 수 있을지 고민하던 홍준이는 너무 어려워서 A와 B의 길이가 짧다면 빨리 풀 수 있을 것으로 생각하고 있습니다.
홍준이를 도와 문제를 해결하는 프로그램을 작성하세요.
첫째 줄에 길이가 5만 이하인 문자열 S가 주어집니다.
둘째 줄에 0 이상 10만 이하인 하나의 정수 Q가 주어집니다.
셋째 줄부터 Q개의 줄에 걸쳐 길이가 1 이상 4 이하인 두 문자열 A와 B가 주어집니다.
모든 문자들은 영문 알파벳 소문자로 구성되어 있습니다.
Q개의 줄에 걸쳐 각각의 두 문자열 A와 B를 부분 문자열로 가지는 S의 연속 부분 문자열의 최소 길이를 출력합니다. 만약 그런 연속 부분 문자열이 존재하지 않는다면 -1을 출력합니다.
xudyhduxyz 3 xyz xyz dyh xyz dzy xyz
3 8 -1