시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 295 | 53 | 44 | 24.176% |
바야흐로 2019년. 아주대학교 알고리즘 소학회 A.N.S.I.는 드디어 동방을 배정받았다!
A.N.S.I. 소학회원들은 새로운 동방을 꾸미기 위해 각자의 예술혼을 불태웠는데, 문자열을 좋아하는 만영이는 벽에 문자열을 하나 장식하고 싶다. 하지만 흔하지 않은 수요라 구하지 못하던 중에, 만영이는 인터넷에서 어떤 문자열 S의 부분 문자열을 판매하는 가게를 찾았다.
부분 문자열이란 원본 문자열의 연속된 일부를 뜻한다. 예를 들어 "acka"의 부분 문자열은 {"", "a", "c", "k", "ac", "ck", "ka", "ack", "cka", "acka"}로 총 10가지가 있다.
만영이가 어떤 문자열이 좋을지 S를 훑고 있던 와중에 뒤에서 구경하던 몇몇 소학회원이 S의 부분 문자열 중 자신이 원하는 문자열을 말하기 시작했다.
사람 좋은 선배인 만영이는 이들의 요청을 무시할 수 없기 때문에, 모든 문자열을 부분 문자열로 포함하는 문자열을 구매하려고 한다. 문자열의 가격은 문자열의 길이에 비례한다. 소학회 예산을 걱정하는 지수를 위해 만영이는 N명의 소학회원이 원하는 문자열 P1…PN을 모두 부분 문자열로 가지면서 가장 짧은 S의 부분 문자열을 주문하려고 한다. 이때 만영이가 주문하게 될 문자열의 길이를 구해보자.
첫 번째 줄에 N이 주어진다. 그 이후 2번째 줄부터 N+1번째 줄까지 P1부터 PN의 길이와 문자열이 순서대로 주어진다. 그 후 마지막 줄에 S의 길이와 S가 주어진다. 모든 문자열은 'a'부터 'z'까지의 소문자 알파벳으로만 이루어져 있다.
S는 P1…PN을 모두 부분 문자열로 갖는다.
조건을 만족하는 S의 부분 문자열의 최소 길이를 첫 줄에 출력한다.
4 2 an 4 anab 2 ab 4 nana 18 bananabananabanana
5
7 4 ajou 4 ajou 7 welcome 2 to 4 ajou 11 programming 7 contest 31 welcometoajouprogrammingcontest
31
2 7 insider 4 acka 53 superduperinsiderkinggodackaemperorgeneralchungmugong
18
아주대에는 전설로 내려오는 최강의 인싸가 존재한다.
University > 아주대학교 > 2019 아주대학교 프로그래밍 경시대회 APC > Div.2 F번