시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 144 39 29 22.656%

문제

어떤 긴 문자열이 주어지고 여러 개의 짧은 문자열들이 주어질때 이때 짧은 문자열을 긴 문자열에 붙여 넣을때 가장 길게 붙여 넣는 경우를 찾아라. 단 이때 짧은 문자열들끼리는 교차 할 수 없다. (‘aabbc'  에  'aab' 와 'bbc' 둘 다 붙여 넣는 것은 불가능하다.) 또, 짧은 문자열은 여러 번 사용할 수 있다.

 

입력

첫 번째 줄에는 가장 긴 문자열이 주어지고 두 번째 줄에는 짧은 문자열의 숫자 N(1 <= 500)이 입력으로 주어진다. 두 번째 줄부터 N개의 줄에는 짧은 문자열이 주어진다.

가장 긴 문자열의 길이 L은 (1≤ L≤100,000) 짧은 문자열의 길이 l은 (1≤l≤10,000)이다.

 

출력

붙여 넣은 짧은 문자열들의 길이의 총합을 출력한다.

 

예제 입력

aabcc
2
aab
bcc

예제 출력

3

힌트

출처

  • 빠진 조건을 찾은 사람: suhgyuho